Првобитниот храм скопјани го граделе пред и по Првата светска војна и бил осветен во 1926 година. Во земјотресот во 1963 година црквата имала оштетувања кои не биле сериозни за да биде урната, но на почетокот на 1970тите години храмот бил миниран и на местото каде што стоел денеска е дел од Градскиот трговски центар. Нестор Алексиев го изработил еднокрилниот, одмерено расчленет и обликуван иконостас, висок неколку метри, а широк околу 10 метри. Денес делови од овој иконостас се наоѓаат во црквата „Св. Петар и Павле“ во Јурумлери, и во „Св. Никола“ во Куманово.
Првобитно возобновување било замислено црквата да се гради на неколку метри од старите темели, односно на самиот плоштад Македонија во Скопје. Но по бурните реакции и несогласувања на муслиманите и атеистите, локацијата била преместена непосредно до Домот на АРМ и недалеку од автентичното место на скопскиот плоштад. Осветувањето на темелите било извршено на 11 ноември 2012 година лично од поглаварот на МПЦ г.г. Стефан во сослужение со митрополитот брегалнички Иларион и свештеници од Скопската епархија. На настанот присуствувале премиерот Никола Груевски, министри од Македонската влада и градоначалниците на Скопје.
