This article proposes a reconstruction, shown in scale drawings, of a palace built for a Malay Sultan, probably in the 1460s. The main aims of the discussion are to clarify the reconstruction, the problems surrounding it, and the reasons for arriving at this form; to place it in the context of region and epoch; and to elaborate on its salient aspects. The article begins with a brief account of Malacca in the 15th century, considers some of the cultural influences on it, and comments on the Malay Annals, a traditional history of the Malacca Sultanate and the sources for the account of the palace on which the reconstruction is based. The description of the building, remarkably lucid considering its age and circumstances, is translated. Various possibilities concerning the overall form of the palace are discussed, particularly two alternatives from the South East Asian area, and one is posited as being the basic forerunner and formgiver. The different parts of the building, particularly those mentioned specifically in the translated passage, are considered relative to the proposed reconstruction.