De Nieuwe Waalse kerk werd even na het midden van de negentiende eeuw gebouwd voor Franstalige calvinisten. Amsterdam heeft eeuwenlang een grote Franstalige gemeenschap gekend, het resultaat van vooral twee immigratiegolven. De eerste dateerde uit de beginjaren van de Tachtigjarige oorlog toen duizenden calvinisten uit de Zuidelijke Nederlanden en Frankrijk de wijk namen naar de Noordelijke Nederlanden. Vooral na de val van Antwerpen in 1585 werd Amsterdam overspoeld door vluchtelingen. De Franstalige calvinisten verenigden zich in de Waalse gemeente en kregen toestemming een voormalige kapel van het Paulusklooster aan de Oudezijds Achterburgwal voor hun kerkdiensten te gebruiken. De gang van zaken in de Waalse kerk verschilde niet wezenlijk van die in andere calvinistische kerken in Amsterdam, alleen dat in de Waalse gemeente Frans de voertaal was.
In 1598 riep koning Hendrik IV het Edict van Nantes uit dat de protestanten in Frankrijk godsdienstvrijheid garandeerde. Koning Lodewijk XIV herriep echter het Edict van Nantes in 1685, en de Franse protestanten, hugenoten geheten, werden voor de keuze gesteld zich tot het rooms-katholicisme te bekeren of de dood. Daarop volgde een nieuwe immigratiestroom van hugenoten vanuit Frankrijk. Van de 50.000 hugenoten die naar de Noordelijke Nederlanden vluchtten, vestigden zich er 12.000 in Amsterdam. Velen van hen vonden werk in de textielnijverheid. Ook het boekenvak was bij hen in trek. Niet minder dan 80 van de 230 uitgevers in Amsterdam in de periode 1680-1730 waren hugenoot.
De toestroom van hugenoten maakte de inrichting van een nieuwe Waalse kerk naast de bestaande aan de Oudezijds Achterburgwal noodzakelijk. In eerste instantie kon een schermschool aan de Prinsengracht, nabij het Molenpad door hen betrokken worden. Vanaf 1808 werd ook een deel van het Walenweeshuis (het tegenwoordige Maison Descartes) aan de Vijzelgracht door de Waalse gemeente gebruikt.
In 1841 kocht de Waalse gemeente een in 1671 door Adriaan Dortsman ontworpen grachtenpand, Keizersgracht 676, met de bedoeling het door een kerkgebouw te laten vervangen. Het duurde daarna nog vijftien jaar eer de nieuwbouw werd gerealiseerd. In 1856 vonden er de eerste kerkdiensten plaats.
De kerk was ontworpen door de architect A.N. Godefroy (1822-1899). Godefroy was een actief lid van de in 1842 opgerichte Maatschappij ter bevordering van de Bouwkunst, en publiceerde regelmatig in het blad van de Maatschappij, Bouwkundige Bijdragen. Daarin betoonde hij zich een voorstander van eclecticisme in de architectuur. In plaats van zich te beperken tot bouwen in één bepaalde historische stijl, zou een architect zijn inspiratie moeten putten uit verschillende stijlen om die naar eigen goeddunken te combineren. Het ging uiteindelijk erom dat de architectuur duidelijk uitdrukking gaf aan de functie en de betekenis van een gebouw, niet of een bepaalde stijl zuiver wordt nagevolgd.
De Nieuwe Walenkerk is een goed voorbeeld van eclecticisme. De gevel is in de classicistische traditie in natuursteen opgetrokken, met een basement uitgevoerd in rustica. Maar de kleine ronde vensternissen en het bogenfries langs de dakrand verraden romaanse invloeden.
Van binnen bestaat de kerk uit een grote rechthoekige zaal geflankeerd door galerijen. De wanden laten een afwisseling zien van pilasters en rondboognissen. Dit alles was traditioneel, maar het materiaalgebruik was eigentijds. De galerijen rustten op gietijzeren kolommen en de houten lichtkap werd gedragen door ijzeren balken. Ook de interieuraankleding liet destijds een mix zien van oude vormentaal en nieuwe technieken en materialen. De klapstoeltjes vertoonden een houtnerftextuur, maar waren in werkelijkheid van gietijzer gemaakt. Voor de verlichting zorgden staande gasluchters, een toen geheel nieuw verlichtingssysteem waardoor het mogelijk werd om de lampen in één keer allemaal tegelijk aan te steken. Later werden de gasluchters bruikbaar gemaakt voor elektrische lampen.
In 1861 werd het interieur door brand geteisterd. De herstelwerkzaamheden stonden onder leiding van wederom Godefroy. De preekstoel en balustrade erboven werden rond 1910 ontworpen, mogelijk door K.P.C. de Bazel.
In 1989 kreeg het gebouw een nieuwe bestemming als kunstcentrum Artemis. In de kerk werd een verdieping ingebouwd waardoor verschillende studio’s voor dans en muziek mogelijk werden. Sinds enkele jaren is het hele gebouw in gebruik bij een reclame productiebedrijf.