The foundation stone was laid on 25^th March 1862 by Dionyssios Charitoniadis, a prelate who late became Oecumenical Patriarch.

The plans were drawn up by Athanassios Moussis, an architect from Epirus. Work was immediately broken off on the outbreak of the Cretan revolution in 1866, but resumed in 1883 and was completed in 1895. Several townspeople offered donations to help build the church, while those unable to do so worked free of charge. The cost came to thirty thousand pounds over and above work offered by the Christians.

The church was consecrated with great pomp and splendour on 16^th April 1895, the Sunday after Easter, by Timotheos Kastrinoyannakis, Archbishop of Crete.

"We doubt whether Heraklion has ever seen a religious feast as splendid and imposing as that which took place at the consecration of the newly erected Cathedral Church of St. Minas. The crowd that had flocked from all over the island was vast, and the decoration of the town without precedent. The fervour of jubilation was beyond description", as a contemporary report vividly puts it.