Pada awalnya, tembok Kota Melaka dibina oleh kerajaan Kesultanan Melayu Melaka mengelilingi Istana Raja. Ia dibina daripada tanah dan diperkuat dengan batang kelapa, batang nibung dan pagar kayu. Manakala kota batu didirikan oleh Portugis (1512) mengelilingi Bukit St.Paul dan siap pada 1548. Ia diperkukuhkan selepas serangan Belanda pada 1605-06.
Kota Melaka mengalami kerosakan akibat serangan pasukan bersekutu Belanda dan Johor. Ia diperkukuhkan lagi oleh Belanda selepas ia menawan Melaka pada 1641. Selain itu, beberapa bastion juga ditambah termasuk Bastion Middleburg di kuala Sungai Melaka.
Namun hampir keseluruhan kota dimusnah oleh Inggeris pada 1806-07 dan yg terselamat hanyalah Pintu Gerbang Santiago. Jabatan Warisan Negara sedang mengkaji kota ini dan pembinaan semula sebahagiannya sedang dilakukan.
Tapak pembinaan Middleburg Bastion di tebing Sungai Melaka tidak jauh dari Tower Clock di hadapan bangunan Stadhuys. Penggunaan batu-batan laterit menjadikan kota ini begitu unik & bakal menjadi salah satu daya tarikan pelancong ke Bandaraya Bersejarah ini.