L'église évangélique luthérienne de la Rédemption a été établie en se réappropriant une ancienne halle de déchargement, ou halle de l'octroi, construite entre 1821 et 1825 par l'architecte Adrien-Louis Lusson[1] et remplacée en 1837 par un bâtiment quai de Jemmappes.
Le la princesse Hélène de Mecklembourg-Schwerin, protestante luthérienne, se marie à Fontainebleau avec Ferdinand-Philippe d'Orléans, fils du roi Louis-Philippe[2]. Le pasteur Rodophe Cuvier, cousin du naturaliste Georges Cuvier, béni le couple royal. La princesse fréquente alors l'église des Billettes, première église luthérienne et siège du Consistoire de Paris depuis 1808, mais le quartier du marais est alors considéré comme dangereux. Pour y remédier, en 1841, la ville de Paris affecte la halle au Consistoire luthérien, et le pasteur Rodophe Cuvier devient le pasteur de la paroisse[3].
Entre 1841 et 1843, l'architecte d'origine allemande François-Christian Gau transforme le bâtiment en conservant ses 4 premières travées sur les onze existantes. Il fait élever le portail, l'abside du chœur, et le clocheton sur la première travée. Après son décès, l'église est terminée par Théodore Ballu.
En 1973, l’architecte protestant Victor Baltard fait aménager les locaux de la maison presbytérale au nord de l'église. Cette même année Paul Gauguin, alors employé chez un agent de change de la rue Laffitte, s'y marie avec une jeune danoise luthérienne, Mette-Sophie Gad (1850-1920)[4],[5].
Le grand crucifix de la table de communion est offert par le baron Haussmann, fidèle de l'église. Il est sans couronne d'épines, les yeux ouverts et la tête et les bras levés vers le ciel. Les obsèques du baron Haussmann ont lieu à la Rédemption le .
L'église possède un orgue Cavaillé-Coll (1844) - Mutin (1912) de 20 jeux, avec 2 claviers de 56 notes et pédalier de 30 notes à transmissions mécaniques. En 1968, l'église luthérienne est expropriée de locaux annexes au sud, pour l'agrandissement de l'Hôtel Drouot.
Charles Gourlier, J.-E. Biet, Edme Grillon, Eugène Tardieu, Choix d'édifices publics projetés et construits en France depuis le commencement du XIXe siècle, Volume 3, p. 8 (lire en ligne) et planche 161 (voir), Librairie Louis Colas, Paris, 1844.