At its inception in 1879, the Cathedral Church of Medan is a leaf-roofed hut and thatched roofed place of worship for dozens of Catholics (the majority ethnic Tamil Indian and the Netherlands) at Jl Pemuda No 1 (formerly: Paleisstraat; Istana Street).

[5] Construction of a new church was initiated in 1905 when the Catholics were numbered 1200 people.

The new church was inaugurated in November of that year, the new church was made of stone walls and tin roof, with some parts still made of thatched palm leaves.

[5] The Tamil Indians later built for themselves a Parish at Jalan Hayam Wuruk in Medan Baru area, called as St. Anthony's Church, annexed to it were housing of Tamil Catholic Indians known as Kampung Kristen or Kovil Kambam in Tamil, Presently Jalan Mataram where the Catholic Center is built.

[5] On January 30, 1928, the church was expanded into its current form following a design by Dutch architect Han Groenewegen.