Kirken er opført i årene 1904-1908 og er tegnet af arkitekten Martin Nyrop (1849-1921) i historicistisk stil. Navnet 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.
Udsnit af Nyrops tegning til Eliaskirken
Kirken blev opført af Det Københavnske Kirkefond, der gennem indsamlinger finansierede byggeriet. Fondet købte en tidligere dansesal, “Valkyrien”, der lå på grunden. Salen blev omdannet til en midlertidig kirkesal, der blev udgangspunkt for hele to kirker, dels Eliaskirken, dels >Mariakirken.
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.
Udsmykningen på alteret er udført af Frans Schwarz.