Денешната улица Македонија во минатото се викала Крал Петар. 

По ослободувањето од турското ропство градот Скопје бил со криви, нечисти и голем број некалдрмисани улици и сокачиња со стари куќи од плитар бондрук. Во тоа време во Скопје немало ниту една улица со голема ширина и право трасирани линии.

За современа изградба на градот биле потребни многу средства. Новата регулација и нивелација на градот помогнале да биде уредена градската сообраќајна мрежа, да се калдрмисаат одредени улици, да се направат улични тротоари.

Една од првите улици што почнале да се градат била улицата Крал Петар. Таа била пробиена во 1911 година и се протегала од Железничката станица до Камениот мост. Била градена со големи правоаголни камени коцки. И тогаш, како и денес, таа претставувала централна улица во градот, на која се наоѓале најпознатите кафеани, продавници.

Корзото на главната улица Крал Петар било душата на градот, каде што на попладневните прошетки секој се однесувал според непишани правила. Сите на корзото знаеле каде треба да се шетаат, во својот дел на улицата. Девојките шетале на средината на улицата, а вљубените парови се шетале на главниот тротоар.

По извесно време, корзото од улицата Крал Петар се префрлало на Џафте корзо кое се простирало од улицата Цар Душан до Железниот мост покрај кејот на реката Вардар. На корзото на улицата Крал Петар по изградбата на улицата шетале млади луѓе со сиромашна облека и ниска култура. Веќе во 1925 година сликата на корзото оддавала пријатна атмосфера, додека во 1935 година улицата Крал Петар била собиралиште на госпоѓици и господа со лакирани чевли, свила и француски парфеми.

По Втората светска војна и создавањето на Југославија, улицата Крал Петар е преименувана во Маршал Тито, а во деведесеттите години на 20 век, го добива денешното име улица Македонија.