Kirken ligger på hjørnet af Willemoesgade og Fiskedamsgade midt mellem kvarterets boligbebyggelser. Den har navn efter Københavns Frihavn.
Kirken første præst, H. P. Mollerup, havde en vis tilknytning til søfarten, da han havde været sømandspræst i England. Han gjorde meget for, at de fattigste i samfundet kunne have kirken som et tilholdssted – en “frihavn”.
Efter århundredeskiftet var boligudviklingen stærk i kvarteret langs Strandboulevarden, så der blev udskilt et selvstændigt sogn fra Sankt Jakobs kirke ved Østerbrogade.
Frihavnskirken blev opført omkring 1906 efter tegninger af arkitekten Thorvald Jørgensen (1867-1946) og finansieret af midler fra Foreningen til Opførelse af Smaa Kirker i København samt midler der blev indsamlet i sognet. Grunden blev skænket af Det Classenske Fideikommis.
