Um 1435 kaufte Jörg von Puchheim drei Häuser an der Freyung, welche er baulich verbinden und zu einer Wohnstätte umbauen liess. Um 1600 wurde das Anwesen von Reichsgraf Karl von Harrach gekauft, und 1658 ging es in den Besitz der Familie Auersperg über. Nachdem das Gebäude während der Türkenbelagerung 1683 niedergebrannt war, kaufte Ferdinand Bonaventura Graf von Harrach das Anwesen und brachte es somit wieder in den Besitz derer von Harrach. Er liess die Brandruine beseitigen und nach Plänen von Domenico Martinelli das heutige Palais bauen. Um 1696 war die Innenausstattung vollendet.

Die Stuckarbeiten stammen von Johannes Piazoll, und Antonio Beduzzi schuf die restlichen Dekorationselemente. Fälschlicherweise glaubte man lange, der Architekt Johann Lucas von Hildebrandt hätte das Palais Harrach erbaut. Von ihm stammte jedoch nur das kleine Salettl, welches auf dem seitigen Vorplatz einst existierte. Damals befand sich hier ein kleiner Palaisgarten, einer der wenigen, welche sich im Stadtzentrum befanden.  Um 1844 liess Franz Ernst Graf von Harrach am Palais umfangreiche Umbauten vornehmen. Um 1850 erneuerte man auch das Innere, was hauptsächlich unter Franz Schönthaler geschah. Nachdem Bomben im Zweiten Weltkrieg grosse Schäden am Palais Harrach verursacht hatten, wurde in den Nachkriegsjahren bis 1952 der ursprüngliche barocke Zustand weitgehend wiederhergestellt.