Stefan Krzysztof Pac, the Lithuanian Grand Scribe, purchased the house and parcel from Hieronim Wołłowicz, the Starosta of Samogitia, in 1628. The Pacs were one of the rising magnate families of the Grand Duchy, and Stefan immediately commissioned a major renovation that wrapped up before 1633. The result was a rectangular palace with a courtyard facade reaching the street and an arched gateway through which a representative hall opened directly onto the city. His son Krzysztof Zygmunt Pac inherited it. In 1655, during the Russo-Polish War, the building burned down. The Pacs rebuilt. Krzysztof Zygmunt's relative Michał Kazimierz Pac, the Grand Hetman of Lithuania who would later fund the magnificent Saints Peter and Paul Church across the Vilnia, took ownership next, and after him came Józef Franciszek Pac, a cousin of Jan Kazimierz Pac.

In 1748 the Baroque palace burned down a second time. Neither Józef Franciszek nor his son Michał Jan Pac, the last male descendant of a once-vast and politically powerful family, could afford to rebuild it on the scale they wanted. Michał Jan Pac was a complicated figure, a man of strong political convictions who in 1771 found himself on the wrong side of the king and the Russian-backed political establishment, and was forced to emigrate. His estates were sequestered. The ruined palace on St. John's Street stood empty until 1783, when Aleksander Michał Sapieha, the Grand Chancellor of Lithuania, acquired it. Sapieha rebuilt and redecorated in the Classical style then sweeping Europe, replacing what remained of the Baroque ornamentation with the cleaner lines of late eighteenth-century neoclassicism.

Aleksander Michał's son Franciszek Sapieha, a General of Artillery, inherited the palace in 1793. After the November Uprising of 1830-1831, the Polish-Lithuanian rebellion against Russian rule that swept the partitioned territories, his son Eustachy Kajetan Sapieha was punished for his involvement. Two years after Franciszek's death, the Russian authorities confiscated the building from Eustachy and made it the seat of the Vilnius Governor, the principal tsarist administrator in the city. From 1909 it served as a Russian club; in 1912 it was rebuilt by the architect Aleksandr Sonin to house the Russian Noble's Assembly. Before the First World War it was the property of the Russian Ministry of the Interior, and at various times its ground floor held a bookstore, an art gallery, and a wine shop.

In 1918, briefly, the Lithuanian Association Rūta met inside its walls. In 1919 it housed the Christian Labor Trade Unions. Polish state institutions occupied parts of it during the interwar years when Vilnius belonged to Poland. After the Second World War, when Vilnius became Soviet Lithuanian and the city's old prewar associations had to be reinvented, the building was assigned to communications workers; for years a long-distance telephone exchange and a telegraph station operated inside it. In 1959 the architects Justinas Šeibokas and Bronislovas Krūminis adapted the building as the Culture House of Communication Workers, with apartments fitted into some wings. Restorations followed in 1978-1991 and again in the 1990s, the latter conducted by the Polish Monuments Restoration Laboratories. On 27 July 2007, Poland purchased the palace outright. It now houses the Polish embassy, the consulate-general, and the Polish Institute in Vilnius, three institutions that together occupy a building that has rarely sat empty since 1628.