Das heutige Grundstück Nr. 13 umfasste ursprünglich zwei Parzellen, die im 16. Jahrhundert Hofangestellten gehörten. Nach einem Brand um 1650/60 ließ Hofarzt Böttcher sein Haus erneuern; die zweite Parzelle bekam er vom Kurfürsten als Geschenk. 1664 kaufte der spätere Cöllner Bürgermeister Heinrich Julius Brandes das gesamte Ensemble und ließ es 1674 zu einem zweigeschossigen Haus mit Mitteleingang und Satteldach ausbauen. Davon sind die Grundmauern und Gewölbekeller bis heute erhalten. Ab 1709 befand sich das Anwesen im Besitz hochrangiger Militärs und Minister. 1710/11 wurde das Gebäude zu Gebäude zu einem Adelspalais mit repräsentativen Raumfluchten ausgebaut.
Nachdem Friedrich Nicolai das Haus 1787 für 32.500 Taler erworben hatte – das wären heute umgerechnet fast vier Millionen Euro– ließ er es nochmals durch Carl Friedrich Zelter umbauen. Damals erhielt das Gebäude sein spätbarock-klassizistisches Aussehen, das sich im Großen und Ganzen bis heute erhalten hat. Im Erdgeschoss wurden Buchhandlung und Verlag untergebracht. Nach dem Umzug der Nicolaischen Buchhandlung in die Dorotheenstraße im Jahr 1891 sollte sich der Charakter der traditionsreichen Ladenlokale im Erdgeschoss des Gebäudes allmählich ändern. Von den weiteren illustren Bewohnern des Hauses zeugen heute noch die zahlreichen Gedenktafeln an der Fassade des Gebäudes.
Der Einzug des Lessing-Museums im Jahr 1910 stellte den wohl gravierendsten Nutzungswandel in der Geschichte des Hauses dar. Mit diesem Datum setzte die Musealisierung von Teilen des historischen Geschäftsgebäudes ein. Gleichzeitig wurde das Nicolaihaus wieder Treffpunkt aufgeklärter und moderner Ideen aus Literatur und Musik.
1936 endete diese Phase abrupt mit der Schließung des Museums durch die Nationalsozialisten. Der Gartenflügel und Teile des linken Seitenflügels fielen später dem Zweiten Weltkrieg zum Opfer.
Die durch Straßenkämpfe beschädigte Fassade des Nicolaihauses wurde ab 1952 wiederhergestellt. Die Innenräume des Nicolaihauses baute man für das Institut für Denkmalpflege der DDR zu Büros und Werkstätten um. Der linke Seitenflügel wurde 1953/54 wiederaufgebaut. Zwischen 1974 und 1984 wurde das Haus umfangreich restauriert. Eine bedeutende Maßnahme war der Einbau des Weydinger-Treppenhauses im Querflügel.
Das klassizistische Kleinod konnte aus dem sogenannten Ermelerhaus in der Breite Straße 11 gerettet werden, als dieses 1967 abgerissen wurde und fand seinen neuen Platz im hinteren Gebäudetrakt des Nicolaihauses. Nach der Wende und trotz Nutzung durch das Berliner Museum für Stadtgeschichte konnte das Haus nicht dauerhaft belebt werden – es stand seit 2007 leer.
Bevor die Deutsche Stiftung Denkmalschutz das Nicolaihaus in ihr Eigentum übernahm, stand das einzigartige Gebäude jahrelang leer – dem Zahn der Zeit überlassen. Dabei ist das Nicolaihaus eines der letzten barocken Wohnhäuser Alt-Berlins, das alle Kriege und Abrisswellen überstanden hat – in der Kaiserzeit, in der Weimarer Republik, den Zweiten Weltkrieg und zuletzt die Nachkriegsmodernisierung der DDR. Nach umfangreichen Vorbereitungen fanden in den Jahren 2014/15 umfassende Sanierungsmaßnahmen durch die Deutsche Stiftung Denkmalschutz statt.
Denn trotz der kontinuierlichen Baupflege machten das hohe Alter des Gebäudes, der Verschleiß insbesondere der seit Kriegsende verwendeten Baumaterialien, Schäden infolge von Umbauten und nicht zuletzt geänderte Bau- und Brandschutzvorschriften eine umfassende Sanierung vor einer weiteren Nutzung erforderlich. So musste etwa die in den 1950er Jahren instand gesetzte Fassade zur Brüderstraße von Grund auf saniert und die Dekontamination des Gebäudes abgeschlossen werden.
Im Zusammenhang damit erfolgten umfassende Arbeiten am barocken Dachstuhl des Vorderhauses. Die gesamte technische Ausstattung und Versorgungsinstallation wurde erneuert und ein zusätzliches Treppenhaus eingebaut. Die gründliche Renovierung und in Teilen Restaurierung umfasste alle Innenräume einschließlich des Haupttreppenhauses und der Weydinger-Treppe. Die Arbeiten erfolgten in enger Abstimmung mit dem Landesamt für Denkmalpflege und wurden im Winter 2015 abgeschlossen.
Die Raumaufteilungen im Erdgeschoss und im ersten Obergeschoss entsprechen dem Vorkriegszustand. Das barocke Treppenhaus stammt noch aus den Zeiten Friedrich Nicolais. Ansonsten zeigt der Vorderhausgrundriss alle Veränderungen des Hauses von seiner ersten Bauphase bis ins 20. Jahrhundert.
Die Deutsche Stiftung Denkmalschutz legte bei den Arbeiten an dem Haus größten Wert darauf, diese baugeschichtlichen Entwicklungen und die Zeugnisse der unterschiedlichen bauhistorischen Epochen zu bewahren. Denn sie haben das Nicolaihaus im Laufe seiner gut 350-jährigen Geschichte entscheidend geprägt.
Nach mehrjähriger Restaurierungsphase konnte das "historischste" Haus Berlins, das Nicolaihaus, im Jahr 2016 wieder eröffnet werden. Am 18.3.2016 wäre der Autor und Verleger Friedrich Nicolai 283 Jahre alt geworden. Zu seiner Geburtstagsfeier hat die Deutsche Stiftung Denkmalschutz herzlich eingeladen. Denn ihr neuer Berliner Sitz in der historischen Mitte der Bundeshauptstadt lebt von der Geschichte Friedrich Nicolais (1733–1811), einem Vater der Aufklärung und Vorreiter des selbstbewussten Bürgertums. In seinem Haus schuf er eine Begegnungsstätte für Politiker, Wissenschaftler und Intellektuelle.
Bis heute lockt das imposante Gebäude viele Besucher an, es ist ein Ort des Austauschs und der Kultur. Im Herbst 2024 kehrte auch die Nicolaische Verlagsbuchandlung wieder in das Haus zurück. Der historische Verlag hatte bereits vor 237 Jahren seine Geschäftsräume im Haus, als Friedrich Nicolai den Verlag und die Nicolaische Verlagsbuchhandlung gründete und selbst hier führte.