Mensen stelden het geloof vroeger boven alles: het ging immers om hun zielenheil! Daarnaast bood het ook een richtsnoer voor het dagelijks leven; de kerk gaf nauwkeurig aan wat goed en wat slecht was. De eerste christelijke kerk die in Haarlem werd gebouwd, was gewijd aan Maria. Het moet een klein houten kerkje zijn geweest, op de Grote Markt, waar nu de Grote of Sint-Bavokerk staat. Na de brand van 1347 werd meteen begonnen met de bouw van een veel grotere, stenen kerk. Daarnaast waren er al enkele kloosters in de stad. Er was ook een 'begijnhof', waar vrome vrouwen samenwoonden zonder in een kloosterorde te zijn opgenomen. Het aantal kloosters zou later toenemen tot een twintigtal. Elk klooster had een eigen kapel of kerk en een eigen begraafplaats. Ook gasthuizen hadden een eigen kapel of kerk. Daarmee was een belangrijk deel van de stad in kerkelijk eigendom. Het geloof was overal in de stad zichtbaar aanwezig. Haarlem viel aanvankelijk onder de bisschop van Utrecht; pas in 1559 kreeg de stad een eigen bisschop. Daardoor werd de Grote Kerk een kathedraal (cathedra betekent 'zetel' van de bisschop).
In heel westelijk Europa heerste de Algemene Kerk van Rome, de 'Roomse Kerk'. In de zestiende eeuw waren er tal van monniken, priesters en intellectuelen die protesteerden tegen wat zij beschouwden als misstanden in de kerk: zij wilden minder pracht en praal, meer eenvoud en een terugkeer naar het oorspronkelijke geloof zoals dat in de Bijbel werd gepredikt. Deze hervormingsbeweging leidde tot snel oplopende conflicten: aan de ene kant werden de hervormers als ketters vervolgd en verbrand, aan de andere kant werd het interieur van kerken vernield (in ons land de Beeldenstorm van 1566) en kloosters geplunderd. Deze religieuze conflicten vormden een belangrijk element in de Tachtigjarige Oorlog (1568-1648), waarin een aantal samenwerkende gewesten (de latere Republiek der zeven Verenigde Nederlanden) zich vrijvochten van de overheersing door het Habsburgse vorstenhuis (Karel V en Philips II). Religie en politiek waren in die periode nauw met elkaar verbonden.
In 1577 verdween het Spaanse garnizoen uit de stad. Haarlem kwam in het kamp van de Opstand en daarmee ook in dat van de Hervorming of Reformatie. Als gevolg daarvan werd de bisschop verdreven en moesten na 1581 alle kloosters gesloten worden. De gebouwen en terreinen werden eigendom van de stad, want voortaan was er slechts één heersende kerk: de Gereformeerde of Hervormde kerk. Die kerk kreeg van de stad ook de beschikking over de bestaande kerkgebouwen. Alle andere godsdienstige richtingen werden verboden. Zo ontstonden de schuilkerken: clandestiene godsdienstoefeningen in schuren, op zolders of in op het eerste gezicht gewone huizen. Dit gold niet alleen de katholieken, maar bijvoorbeeld ook de luthersen, doopsgezinden en remonstranten.
Hierin kwam pas verandering in 1798, toen kerk en staat officieel van elkaar gescheiden werden. Elk kerkgenootschap had voortaan dezelfde rechten, al duurde het nog wel even voordat dit ook volledig werd uitgevoerd. De katholieke kerk kreeg pas in 1853 toestemming om weer haar eigen organisatie in te richten. Omdat menigeen het echter nog steeds te ver vond gaan om de bisschop in de belangrijkste stad van het land (Amsterdam) te vestigen, werd Haarlem opnieuw bisschopsstad. In 1898 werd de nieuwe Kathedraal Sint-Bavo aan de Leidsevaart – gebouwd door Joseph Cuypers met assistentie van zijn zoon Pierre – ingewijd. De bouw werd in 1930 voltooid.