The Red House, now more commonly known as Stadthuys, was the residence and office of the Dutch Governor. The exact date of construction and the architect who built it is not recorded, but it is believed to have been built between 1641 and 1656 (refer to J. Nessel’s map). The building spans 49,200 square feet and stands four stories high along the terraces of Bukit Melaka (St. Paul’s Hill). The original colour of the building was white, but it was painted red around the 1910s.

According to sources from the Dutch era in Melaka, this building was known by various names, such as Gouverneurs Huÿs (1656: J. Nessel), Secretarÿ ende Gouverneurs Wooningk and Beste pakhuÿsen seerschon en accomodabel (1663: anonymous), Gouverneurs Huys (1670: M. Cramer), Governor House (1678: B. Bort), Maison du Gouverneur (1698: F. Froger), Wohnung des Gouverneurs, Wohnung den Zweyten, Negotien Comtoir and Negote Pack Häusser (1744: J.W. Heydt), Government, Secretarye en Negotie Comptoir, negotie Packhuys en swmiswinkel (1792: Reimer), Maison du Gouverneur (1750: N. Bellin), Government House (1795: W. C. Lennon), Government House (1807: E. H. Locker) and Woning des Gouverneurs (1821: Stavenisse de Bruin).

Around 1825, the British continued using the building as a government office. At that time, it was known as Stadt House (1834: P. J. Begbie), (1865: J. Cameron), (1907: F. Swettenham) and (1908: A. Wright), Stadthouse (1839: T. J. Newbold), (1847: J. B. Jukes) and (1894: N. B. Dennys), Stadhouse (1847: C. Dyce) and Stadthaus (1879: I. L. Bird) and (1914: FMSR Pamphlet of Information for Travellers). It is unclear why the British used the term "Stadt," a German word, while "Huys" might have been adapted from Dutch. Subsequently, it continued to be known as Stadthuys until today.

After the independence of the Federation of Malaya, the building continued to serve as the office of the Chief Minister of Melaka and various government offices until 1979. The local community of Melaka knows it as the Government Office, the Red Building, or the Red House.