In the 13th and 14th centuries there were stone structures within the palace site; some archaeologists believe that a wooden palace stood there as well. The stone palace was built in the 15th century, apparently after a major fire in 1419. The existing stone buildings and defensive structures of the lower castle, which blocked the construction, were demolished. The palace was built in Gothic style. The keep of the upper castle, as well as the palace, were meant to host the coronation of Vytautas the Great. The Gothic palace had three wings; research suggests that it was a two-story building with a basement.