If you've tried every whitening method and your shoes are still looking soiled and drab, it might be time to purchase a new pair. It's generally a good idea to replace your shoes every 300–500 miles, so if you've been walking and running in your trusty kicks for about six months, you may benefit from a new pair regardless.