The most representative residential building in Stobi is located in the center of the town, between the streets of Via Principalis Inferior and Via Principalis Superior. The name was applied by the assumption that the emperor Theodosius I was accommodated here during his visit of Stobi in 388 AD.
The palace is divided in two parts which are not linked by common entrances. The south part is called House of Parthenius because of a seal inscription reading “Of Parthenius”. Having in mind that the Palace is not excavated completely and probably the so – called “Prison” also belonged to the complex, more appropriate name for the building is Theodosian Palace.
The north part is the more attractive area of the palace. The rooms with mosaic floors are arranged around the open court surrounded by columns (peristyle). The floor of the court and the corridors around it, also have mosaic floors. At the eastern end of the peristyle there is a pool fenced with pink marble parapet blocks. Above the pool there are niches and marble bases once decorated with sculptures. The famous bronze satyrs from Stobi are exhibited in the National Museum in Belgrade, as well as the bronze sculptures of Apollo, Aphrodite and Lar and the marble head of Serapis. These artifacts were discovered inside the pool as a result of destruction. It is interesting to point out that some of them, such as the satyrs, were made during the Hellenistic period (2nd century BC) and the palace was built in the 4th century AD.
There is also a peristyle in the south part of the palace. Around this small court there are a few rooms. Two of them have mosaic floors and one of them served as a storage room judging by the ten discovered pithoi.
To the southeast of the palace, two vaulted chambers were discovered. Because of the human remains they are called “Prison”. Some of the older scholars consider these facilities to be a cellar and thus a segment of the economic part of the palace.
The palace was destroyed during the 5th century AD after what the walls were incorporated in the poor houses, built on top of the ruins in the 6th century.