It is formed from the reclamation of land around an islet named Jawa Island (Malay: Pulau Jawa, not to be confused with Indonesia's Java Island and originally a tidal island) in the mid-1990s, when the Malacca State Government under then Chief Minister, Abdul Rahim Thamby Chik was planning to turn it into a "Malacca Manhattan" for business and recreational purposes.

Various historical accounts stated that the island was used as a battery by Acehnese, Portuguese and Dutch forces between the 16th and 17th century.

It became part of the RM 2 million "Twin Island City Centre" waterfront project undertaken by Pulau Kembar Sdn Bhd (formerly Inno Enhance Sdn Bhd), a defunct joint-venture of Larut Consolidated Berhad and Talam Corporation Berhad, which involved the reclamation of two islands measuring 40ha and 50ha respectively and launched in May 1996 by then-Prime Minister Mahathir Mohamad.

This project was planned to comprise mixed residential and commercial development together with leisure-cum-tourism amenities such as marine theme park, marina, hotels and waterfront activities.

[5][6] Following the subsequent abandonment of its twin-island project by the original developer in the late-1990s due to Asian Financial Crisis,[7] KAJ Development Sdn Bhd intervened and revived the project under the name of Melaka Gateway in 2014.