Kirken er opført i årene 1904-1908 og er tegnet af arkitekten Martin Nyrop (1849-1921) i historicistisk stil.
Dens navn er hentet fra profeten Elias, der ses afbilledet over hovedindgangen.
Efter at befolkningstallet på Vesterbro var steget i anden halvdel af 1800-tallet, var der behov for at opføre flere nye kirker i det tæt befolkede kvarter.
Da Nyrop tegnede kirken, var han inspireret af den romanske kirke i den sjællandske landsby Tveje-Merløse, som Eliaskirken ligner i både det indre og det ydre.
Kirken blev opført af Det Københavnske Kirkefond, der gennem indsamlinger finansierede byggeriet. Indtil kirken stod færdig, brugte man det nedlagte danseetablissement “Valkyrien” på Vesterbrogade som kirkesal.
Adgangen til kirken sker af en bred stentrappe fra torvet udenfor. Selve kirkerummet ligger så at sige “på 1. sal”, og kirkegængere oplever det som ophøjet i forhold til verden udenfor.
Samtidig er der blevet plads til en kirkesal nedenunder. Dermed udnyttes arealet på den smalle grund mellem beboelseshusene optimalt.
