The Musjid boasts a history extending over 1200 years. The earliest European mention of the Musjid is found in a description from November 1505 when a Portuguese expedition commander anchored in Colombo bay. In 1520, after an attack on the Portuguese trading post established earlier by Lopo de Brito, Captain of Portuguese Ceylon, King Bhuvanaikabahu of Kotte burned down the town of Colombo along with two large Musjids. The Musjid, however, was swiftly rebuilt on the same site.

In the 1820s, the Musjid was redesigned and reconstructed by Malay architect Muhammad Balangkaya, the son of a Malay noble from the Royal House of Gowa (present-day Sulawesi, Indonesia), who had been exiled to Ceylon in 1790 by the Dutch. This reconstruction resulted in a two-storey structure, one of the first of its kind. In 1826, the British Governor of Ceylon, Edward Barnes, visited the Musjid and praised the architect for his exceptional work. In 1827, Sir Alexander Johnston discovered an Arabic-inscribed tombstone dating to 948 AD, moved by the Dutch from the old Muslim cemetery next to the Grand Mosque, suggesting that the Musjid may be over 1,100 years old and potentially the oldest Musjid in Sri Lanka.

In 1897, an additional wing was built under the supervision of I. L. M. H. Muhammad Mohideen. This wing was later used in 1959 as classrooms for the newly established Al-Madrasathul Hameedia school. In 1921, the school’s name was changed to Hameedia Boys’ English School. The Musjid underwent further reconstruction during the 1900s to accommodate the modern needs of the Muslim community.

The Musjid also houses the shrine of the Malay saint, Bahu-Uddeen Tuan Bagoos Balankaya.