PaulusbroederkloosterDe Waalse Kerk is een van de weinige restanten van de kloosters die in de middeleeuwen op de Oudezijds stonden. De kerk is de vroegere kapel van het Paulusbroederklooster dat werd gesticht in 1409 en stond op een groot terrein tussen de Oudezijds Achterburgwal, Oude Hoogstraat, Kloveniersburgwal en Dwarsspinhuissteeg. Na de stadsbrand van 1452 werd de kapel gedeeltelijk herbouwd en uitgebreid, waarna hij in 1496 gewijd kon worden. Door de reformatie liep het aantal kloosterlingen echter snel terug, zodat delen van het terrein aan de stad verkocht werden. Na de Alteratie (1578) werd het klooster door het stadsbestuur geconfisqueerd en moesten de zes overgebleven kloosterlingen elders hun heil zoeken.
In de loop der jaren veranderde het aanzien van het kloosterterrein sterk, omdat er diverse gebouwen op gebouwd werden. Een voorbeeld daarvan is het Oost-Indisch Huis dat kwam te staan op de plek waar eerder de boomgaard van het klooster had gelegen. Tegenwoordig rest alleen de kloosterkapel nog. Hij werd na de Alteratie enige jaren gebruikt als opslagplaats en proveniershuis, een liefdadig gesticht. Maar in 1586 kreeg de Waals-hervormde gemeente toestemming om in de kloosterkapel Franstalige kerkdiensten te houden, waardoor de kapel zijn oorspronkelijke functie terugkreeg.
De Waals-hervormde gemeente bestond uit Franstalige gereformeerden of Hugenoten, die enerzijds uit angst voor de Katholieke repressie, anderzijds uit economische overwegingen uit de Zuidelijke Nederlanden en Frankrijk naar Amsterdam waren gevlucht. Toen zij de kapel in gebruik namen werd hij omgedoopt in "Walenkerck" of Waalse Kerk.
De kloosterkapel die de Hugenoten betrokken bestond uit een middenbeuk en een noordelijke zijbeuk. Op den duur was hij te klein om de groeiende gemeente te herbergen en werd de kerk uitgebreid. In 1647 vonden herstellingen plaats en werd het westelijke ingangsportaal gebouwd in een classicistische stijl. Vervolgens werd de kerk in de jaren na 1661 met een zuidelijke zijbeuk uitgebreid. Daardoor kreeg de Waalse Kerk zijn huidige vorm: een driebeukige kerk, overkapt met houten tongewelven en ondersteund door ronde zuilen met achthoekige kapitelen (waarvan het bladwerk later is verwijderd). Opvallend is dat de vormen van de nieuwe zijbeuk zorgvuldig aan de gotische stijl van de middeleeuwse kerk werden aangepast. Het orgel dateert uit 1680 en werd in 1734 vergroot door de beroemde orgelbouwer Christian Müller. Het is het best bewaarde Müller-orgel.
Aan de noordzijde van het voormalige kloosterterrein staat tussen de woonhuizen aan de Oude Hoogstraat het zogenaamde Walenkerkspoortje (1616) dat wordt toegeschreven aan Hendrick de Keyser. Het poortje is versierd met doodshoofden, een verwijzing naar de uitvaarten die aan deze zijde van de Waalse Kerk plaatsvonden.
De kerk werd in 1817 en 1891 verbouwd en gerestaureerd, waarbij de gevel aan het Walenpleintje vernieuwd werd. Deze nieuwe gevel kwam niet in de plaats van de oude, maar werd in een neo-renaissancistische stijl tegen de oude gevel aangemetseld.
Een volgende restauratie vond plaats in de jaren 1949-1951, waarna in 1990-1992 de kerk opnieuw werd gerestaureerd. De aanleiding voor deze restauratie was de zorgelijke staat waarin de constructie van het gebouw verkeerde. De kerk was verzakt, waardoor scheurvorming in de gevels en in de zandstenen zuilen was opgetreden. Een van de oorzaken van de verzakking was de negentiende-eeuwse gevel die voor de kerk was gezet. Een andere oorzaak vormden de technische aanpassingen uit de jaren zestig van de twintigste eeuw, toen op een te zware vloer van stalen balken een betonvloer was gestort. Behalve funderingsproblemen waren er ook stabiliteitsproblemen in de kap van de noordbeuk. De naar buiten werkende krachten (de zogenaamde spatkrachten) in de kapconstructie drukten de noordgevel naar buiten en de kolommen naar binnen.
De restauratie van de kerk bestond voornamelijk uit het herstellen van het oorspronkelijke krachtenspel. De betonnen vloer werd verwijderd en maakte plaats voor een nieuwe, zelfdragende vloer die onafhankelijk van de rest van het kerkgebouw werd gefundeerd. Onder de gesloopte vloer lagen nog veel van de oorspronkelijke grafzerken, die op de nieuwe vloer werden aangebracht. Bij het herplaatsen van het meubilair is de dooptuin weer in de oorspronkelijke vorm neergezet. Ook het balkon werd in oude luister hersteld. Omdat de kerk bijzonder geschikt is voor concerten en cd-opnames, is veel aandacht besteed aan het behoud van de akoestiek van de ruimte.