General rule of thumb: running shoes should last between 900 to 1000 miles, or roughly 1500 kilometers. Though keep in mind that every runner is different!  Shoes will wear out differently depending on running style, terrain and shoe material. Also, note that the shoe's design integrity (like midsole support) become less effective after the 1000 mile mark.