At the same time St. Magnus Cathedral was being built (in Kirkwall), the Bishop's Palace was built. It is the only episcopal palace ever built in Norse Scotland and housed the cathedral's first bishop, William the Old of the Norwegian Catholic Church. The great Haakon IV of Norway died in the Bishop’s Palace in 1263, a momentous event in its history. The neglected palace fell into severe ruin by 1320. The palace was renovated in 1541 and occupied by bishops until 1688.
Welcome to Bishop's and Earl's Palaces
The ruined structure looks like a small castle. 
Earl's Palace was added much later, in the 1600's. It was built after Patrick, Second Earl of Orkney, decided the Bishop's Palace was inadequate for his needs. He had a terrible reputation and was eventually beheaded for treason. Earl's Palace fell into ruin in the 18th century.
The Earl's Palace, c. 1600's
Palace ruins