Bangunan Stadthuys yang bermaksud Dewan Bandaran dibina oleh pemerintah Belanda pada tahun 1650an setelah mengambil alih Melaka daripada Portugis pada tahun 1641. Bangunan setinggi empat tingkat mengikut teres Bukit St. Paul seluas 49,200 kaki persegi, menjadi kediaman Gabenor Belanda sehingga awal kurun ke 18 di samping menjadi pusat pentadbiran Belanda sehingga 1824. Pemerintah Inggeris menjadikan bangunan ini sebagai pusat pentadbirannya. Bangunan Stadthuys terus menjadi pusat pentadbiran negeri Melaka hingga akhir tahun 1979. Warna asal bangunan ini adalah putih. Ianya ditukar kepada warna merah pada tahun 1920an dan kekal sebagai Bangunan Merah.

Bangunan Stadthuys telah mengalami banyak perubahan sejak awal Zaman British. Walau bagaimanapun ia masih mengekalkan seni bina Belanda dengan ciri-ciri seperti dinding batu yang tebal beserta tingkap-tingkap dan pintu-pintu yang besar. Di bawah lantai bangunan ini disediakan sistem perparitan yang dialirkan ke Sungai Melaka. Di ruang pejabat Gabenor terdapat hiasan ukiran kayu keras berbentuk bunga. Dapur tempat membakar roti yang besar terletak di belakang menunjukkan ramai orang yang berkunjung. Ruang bilik tidur Gabenor yang terletak pada bahagian paling tinggi dihias dengan lukisan mitologi Cina. Di bahagian bawah hadapan terdapat ruang penjara.

Konservasi bangunan Stadthuys telah dilaksanakan pada tahun 1985 oleh Jabatan Kerja Raya Melaka, mengambil masa selama 4 tahun. Semasa kerja-kerja tersebut dijalankan telah terjumpa beberapa komponen yang tidak diduga. Antaranya ditemui perigi yang disusun dengan batu karang di kawasan halaman bahagian dalam dan sebuah lagi di bawah tembok bangunan yang telah dikambus semasa bangunan tersebut dibina. Kedua-dua perigi ini dipercayai digali pada zaman Portugis. Selain itu, sebuah perigi Belanda beserta tapak bangunan yang dibina seiring dengan bangunan Stadthuys telah ditemui, di bahagian belakang, sebuah kolah dan laluan dari dalam bangunan telah ditemui semasa kerja-kerja memusnahkan ruang tambahan baru. Kesemua penemuan ini diwujudkan semula untuk tatapan orang ramai.