Im Jahr 1559 gründete Papst Paul IV. die Diözese Haarlem durch die Bulle "Super universas" als Suffragandiözese der Erzdiözese Utrecht. Die Diözese umfasste die damalige Grafschaft Holland, ungefähr das heutige Nord- und Südholland. Dem Bistum war kein langer Bestand beschieden: 1578 fiel Haarlem in die Hände der Calvinisten und Bischof Van Mierlo musste aus der Stadt fliehen. Das Bistum wurde 1592 formell abgeschafft.
Als die bischöfliche Hierarchie 1853 wiederhergestellt wurde, wurde Haarlem wieder eine Diözese. Unter Bischof Johannes Huibers wurde die Diözese 1955 stark verkleinert: Die Provinz Südholland wurde in eine neue Diözese Rotterdam abgespalten, die Provinz Zeeland wurde der Diözese Breda hinzugefügt und die Watteninseln Vlieland und Terschelling wurden der neuen Diözese Groningen hinzugefügt.
Während des Episkopats von Theodorus Zwartkruis wurde das Priesterseminar in Warmond geschlossen und durch ein Theologisches Kolleg in Amsterdam und Pastoralschulen in den Dekanaten ersetzt. Das Willibrordhuis-Seminar wurde 1997 von Bischof Henricus Bomers in enger Zusammenarbeit mit seinem Weihbischof Jos Punt gegründet. Im Jahr 2004 wurde Mgr. In De Tiltenberg ein neues Schulungszentrum gebaut.
Anlässlich des 450-jährigen Bestehens der Diözese im Jahr 2009 wurde der Name der Diözese in Haarlem-Amsterdam geändert. Diese Namensänderung steht im Einklang mit der inoffiziellen Faustregel, dass Bistümer den Namen der Hauptstadt verwenden, auch wenn sich der Domsitz nicht in dieser Stadt befindet (vgl. das Bistum Mechelen-Brüssel). Bischof Punt sagte in einer Erklärung, dass die Änderung ein gutes katholisches Zeichen für den Rest der Welt sei, "aufgrund des Bekanntheitsgrades Amsterdams, seiner reichen katholischen Geschichte, die durch das Wunder von Amsterdam geprägt ist, und seines Charakters als multireligiöse Stadt." Der neue Name wurde durch päpstliches Dekret vom 7. Oktober 2008 gewährt.
Geleitet wird das Bistum seit 2020 von Bischof Johannes Willibrordus Maria Hendriks. Er ist der 14. Bischof des Bistums. Hendricks, geboren am 17. November 1954 in Leidschendam, wurde am 29. September 1979 zum Priester geweiht. Bevor er 2011 zum Weihbischof und Titularbischof von Arsacal ernannt wurde, war er Rektor des Priesterseminars De Tiltenberg. Am 1. Juni 2020 erfolgte die Bischofsweihe.
Bischofssitz ist die St.-Bavo-Kathedrale in Haarlem. Konkathedrale ist die Basilika St. Nikolaus in Amsterdam.