A bishop's residence existed in Mdina in 1445, and amongst other functions it housed the diocese's archives (Archivum Archiepiscopalis Melitensis, AAM).

The residence and administrative seat moved from Mdina to a second Bishop's Palace in the capital city of Valletta in the mid-1630s.

[2] The present building was constructed between 1718 and 1720 according to the designs of architect Lorenzo Gafà, shortly after the reconstruction of the adjacent St Paul's Cathedral.

The capitulation document was signed within the palace, and on the same day French general Claude-Henri Belgrand de Vaubois and his staff were invited to dine with Bishop Vincenzo Labini.

[4] The palace is built within a restricted site in Archbishop's Square directly adjacent to the Cathedral and the city's fortifications.