This article examines a group of previously unpublished floor plaster fragments together with architectural and stratigraphic evidence from the Main Building of the Palace of Nestor at Pylos. Analysis of the plaster shows that the fragments formed part of the floor of upper-story rooms, which fell during the building's structural collapse. This study confirms an earlier hypothesis that the majority of the Main Building carried an upper story and also indicates that the palatial megaron did not have an upper story or balcony. The evidence from Pylos is considered in light of Late Bronze Age comparanda, allowing for a revised reconstruction of the Mycenaean palatial megaron.