The original church was consecrated to the Virgin Mary by the Right Reverend George Frederick Hose, the Bishop of Singapore, Labuan & Sarawak, on 13 February 1887.

This structure was built of timber on Bluff Road, on top of a hill now known as Bukit Aman, where the headquarters of the Royal Malaysian Police is now located.

It served as the centre for worship and spiritual life for the small group of Anglicans around Kuala Lumpur at that period.

In 1893, a decision was made to erect a new building to house the growing congregation, and a new site was found beside the Padang or Parade Ground (now known as Dataran Merdeka or Independence Square) of the Selangor Club.

Notable local contributors to the building fund included personalities like Yap Kwan Seng and K. Thamboosamy Pillay, even though they were not Christians themselves.

On 9 February 1895, the 'first brick church erected in the native States of Malay Peninsula' was consecrated by the same Bishop.

Further redevelopment of the cathedral has resulted in the Multi-Purpose Hall, as well as additional offices for the clergy and a studio apartment.

The organ was originally purchased by Frederic Duberly, the Federal Commissioner of Lands & Mines and the Acting Resident of Pahang for his personal use in 1898 at the cost £381/12s,/8d.

Duberly died of a heart attack on 3 April 1903, and his organ was packed up and shipped to Kuala Lumpur.

It was badly damaged again during the Second World War necessitating a complete rebuild in 1951, making the organ more Riddell than Willis by then.

The church is accessible within walking distance north west of Masjid Jamek LRT Station.