The Muddy Way is one of the four straight streets which starts at the unnamed great square in the center of King's Landing (the three others being: the King's Way, the Gods' Way and the Street of the Sisters). It's original name was the Blackwater Way but the smallfolk soon renamed it.
King's Landing rapidly grew without any planning during the first century following Aegon's Conquest, so much so that by the reign of King Jaehaerys I Targaryen it became a problem; the streets were close, dark and filthy. In 52 AC Jaehaerys I ordered the start of works to widen, straighten the streets and cobbled them where possible. Jaehaerys also built a great central square carved out and planted with trees, with markets and arcades beneath. From this square sprung the Muddy Way.