Камено здање Вождовачке цркве неупадљиве величине и архитектуре, какво се често виђа код нас, сакривено је на малој парцели окруженој високим зградама. Осим оних којима је то парохијска црква, осталим Београђанима она углавном служи као оријентир у дугачким улицама Војводе Степе и Јове Илића.
О њој би се могло писати као о просечној српској цркви XX века, само да није једног изузетног детаља, који је чини једном од најзанимљивијих богомоља Србије, чуварем ремек-дела уметности претходног столећа.
Данашње црквено здање друго је на овом месту. Прва црква изграђена је 1911. године, на тадашњој далекој периферији Београда, тако забаченој да још наредне две деценије неће доспети у планове града. Сиротиња која је ту живела – фијакеристи, ковачи, млекаџије, радници и ситне занатлије – свакако себи не би могла приуштити грађење цркве, па се на тај богоугодан потез одлучио трговац Јова Јовановић, који је цркви поклонио своје земљиште. Када се, поведена његовим примером, овоме прикључила и Београдска општина са својим плацем, добијено је довољно простора за храм и малу порту око њега, па се почело са зидањем.
Парохијани су издвајали од својих скромних примања, а додавали су они који су имали и више него довољно, попут индустријалаца Ђорђа Вајферта и Јована Вшетечке, док је велико звоно за још увек дрвену звонару купио извесни Пјетро Казагранде. Када је завршено, било је то једнобродно здање сведених линија, са непропорционално малом куполом – права сеоска црквица, у складу са својим окружењем.
Четири године по освећењу, црква је у рату девастирана, а њен скромни мобилијар опљачкан. У послератном Београду, у којем је ваљало поправити много тога, обнова Вождовачке цркве дошла је на ред тек 1926. године. Мала црква је после живела свој скромни живот све до 1970. Након постепеног отопљавања односа цркве и државног руководства, приступа се обнови храмова, али и изградњи нових тамо где их није било, или где су у Другом светском рату порушени.
Главни украс цркве је звоник над улазом, са завршетком у облику кубета.
Овај покрет водио је патријарх српски Герман, који је покренуо иницијативу да се и Вождовачкој цркви, чија се парохија знатно увећала, да нови изглед. Током лета 1970. године стара црква је корак по корак рушена, а нова је, према плановима архитекте Драгомира Тадића, расла из старе. Иако на потпуно истој локацији, нови храм је знатно већи од свог претходника, продужен за читавих седам метара ка западу. Нова грађевина је типична за радове архитекте Тадића, који је сличне цркве подигао широм Југославије: ослањајући се на искуства међуратних градитеља, Тадић се служио модернизованим речником средњовековних мајстора, са доста лукова, бифора и обавезном розетом над улазом. Главни украс цркве је звоник над улазом, са завршетком у облику кубета. Све радове надгледао је и саветом помагао патријарх лично.
По завршетку грађевинских радова прешло се на декорацију унутрашњости храма, па је под поплочан студеничким мермером, а иконостас, рад охридских дрворезаца, осликао је академски сликар Милосав Младеновић, који се водио средњовековним узорима. Најлепши утисак оставља мозаик у лунети над улазним вратима: по одабиру патријарха Германа, узет је предложак из Цркве Светог Ахилија у Ариљу, па је по нацртима сликара Живка Стоисављевића ово вредно уметничко дело израдио професор Антонио Орсини из Венеције.
Остало је још да се црква живопише. На ово се чекало до 1987. године, када је патријарх Герман за то благословио Милића Станковића, познатијег као Милић од Мачве. Овај академски сликар се до тог времена већ прочуо својим надреалистичким призорима, који су се храбро, и за то доба врло неуобичајено, бавили темама из српске прошлости на врло директан начин. Неконвенционалан у свему што је чинио, Милић од Мачве одлучио је да и у православни живопис овог храма унесе новине тако што ће му дати свој особени печат. Тако на Тајној вечери лете балвани, тај неизоставни мотив његових слика.
