Construction of the palace began sometime between AD 75 and AD 80. Archaeologists were able to follow the building process of the palace by dating the pieces of pottery and coins left behind by the craftsmen .

Roman soldiers who abandoned the site, left behind buildings, roads and a harbour after its construction, first used the plot of land as a military base. The roads were later resurfaced and the drainage and harbour were improved. Before the Palace at Fishbourne was built, the military buildings were dismantled and the area, where the easterly granary stood, was redeveloped with a timber dwelling containing 12 rooms.

Around AD 65-75, a guesthouse was built with a new villa, complete with built-in baths, also known as the ‘proto-palace’ (picture to the left). This newly erected building was made more elaborately out of stone than the timber dwelling that was demolished. This later became the southeast corner of the palace. This was also the time when the southern road was constructed and the stream to the west was widened.