The passage everyone reaches for is Regimen II.lxii, quoted in the 1931 Loeb translation as “Walking is a natural exercise, much more so than the other exercises.” Stop there and it sounds like the slogan. It does not stop there: the sentence continues “… but there is something violent about it.”
King notes that the statement has to be read against the preceding chapter, which sorts exercises into ‘natural’ (kata physin) and ‘violent’ (dia biēs) — and that the natural exercises listed there are not walking at all, but sight, hearing, voice and thought, all of which ‘move the soul’. Her conclusion is that this is “clearly not the world of sports medicine” that the modern slogan belongs to.
There is a further complication about who Hippocrates even is here. King records that Galen already doubted that the first book of Regimen was Hippocratic, allowing only that the second book “might perhaps with good reason be thought worthy of Hippocrates” — and modern scholarship attributes none of the corpus to him with confidence.