År 1955 beslöt Enskede kyrkofullmäktige att utlysa en arkitekttävling för den nya kyrkan Man bjöd in fem arkitekter, Georg Varhelyi, Peter Celsing, Hans Asplund, Ture Ryberg och Sigurd Lewerentz. Det var Sigurd Lewerentz som fick uppdraget att rita kyrkan. Det första spadtaget togs den 29 mars 1958 och arbetet med Markuskyrkan blev ett för moderna tider ovanligt projekt. Det etablerades nämligen en gamla tiders byggnadshytta, där arkitekten dagligen ledde arbetet. Lewerentz uppmärksamhet riktades speciellt mot arbetsuppgifterna hos murarna, som respekterade hans kreativitet och kunskap. Invigningen skedde den 8 maj 1960. I denna byggnadshytta uppstod flera anekdoter som illustrerade att Lewerentz' kunde vara mycket bestämd. En plattsättare tyckte, att om han skulle göra så som Lewerentz ville, så “fick han det inte rakt”, varpå Lewerentz svarade: “Rakt och rakt, varför skall allting vara rakt? Det skall vara vackert, även om det är krokigt.” Och med en plåtslagare hade han följande ordväxling. Plåtslagaren: “Jag kan väl göra som jag brukar?”, Lewerentz: “Nej, det är det enda jag vet, att du inte skall göra!” Kyrkan väckte stor uppmärksamhet redan under byggtiden både i Sverige och utomlands, och 1962 fick Sigurd Lewerentz för Markuskyrkan det första Kasper Salin-priset som utdelats. I Björkhagens kyrka använde Lewerentz första gången karmlösa fönster. Isolerglasrutorna sattes med hjälp av elastisk fogmassa direkt i muröppningen. Det finns inga dörrfoder, socklar eller täcklister och de elektriska ledningarna är dragna synliga utanpå murverket och bildar ett eget arkitektoniskt uttryck. Målningen är ytterst sparsam, ytskikten domineras av naturmaterial, tegel från Helsingborgs Ångtegelbruk, golvklinker från Höganäs, limträbalkar och plywoodskivor. Större delen av belysningsarmaturer och bänkarna är formgivna av Lewerentz själv. Kyrkorgeln är även den formgiven av Lewerentz, med sidostycken av plywood. Utsmyckningen i Markuskyrkan skapades av konstnärsparet Barbro och Robert Nilsson. De formgav bland annat de två vävnaderna bakom altaret och krucifixet däremellan. Kyrksilvret, ljusstakar och bronsplattan i träporten är skapade av Robert Nilsson, likaså en klinkerrelief i fasaden ovanför porten. Inom fastigheten finns även samlingslokaler och pastorsexpedition runt en gård med en spegeldamm med en bronsfontän, Lotusblomman av Robert Nilsson. I en sidobyggnad invid församlingsexpeditionen finns ett klocktorn med fyra klockor. Sedan kyrkan invigdes 1960 har man använt sig av manuell ringning. För den manuella klockringningen varje helg svarar Markusringarna som är en ideell organisation. En femte klocka är placerad utanför kyrkporten. Den används speciellt vid helgmålsringningen varje lördag kväll kl. 18.00.