London, in case you were wondering.
It all began with a 1764 survey of the local infrastructure by the Commission of Sewers and Pavements (one can only imagine the sins a bureaucrat had to commit to end up on the sewer commission). The commission found that London roads were “defective, even in the principal streets.”
Apparently 18th century Londoners hated walking on cracked pavement and muddy roadway shoulders as much as we do today, because a year later concerns over the commission's findings prompted the creation of the city's first curbed sidewalk. Other cities followed suit, and by 1823 Paris had even enacted a law requiring property owners to install sidewalks adjacent to their buildings. (No one paid much attention to it, as these were the days before binding developer agreements.)
Of course, pedestrians had been on the minds of city leaders long before the apperance of sidewalks. Heavy traffic congestion led Julius Caesar to ban the use of cars and chariots between sunrise and sunset on the roads of ancient Rome--though (no big surpise) he reneged on an earlier promise to grant pedestrians the right of way over other road users. Nor did other pledged improvements, such as road paving, ever materialize.
In fact, it wasn't until 1,000 years after Caesar's reign that paving began in earnest throughout Europe (Paris began the trend in the late 1100s). Paved roadways made walking easier for pedestrians in medieval cities...but it also made walking easier for horses, oxen, and other types of "heavy vehicle" traffic.
The increasing chaos on city streets got architects thinking about how to design city transportation networks that served everyone. Leonardo da Vinci recommended that the problem be addressed by separating pedestrians from other forms of traffic. Here is one of his drawings from the late 1400s, showing how the concept might look:
Although his designs weren’t adopted at the time, da Vinci's vision of pedestrian-only spaces was prescient-- today you can find "pedestrianized" streets everywhere from New York to Costa Rica.