Christianity in the region of Strumica began to spread during the first centuries AD. Strumica, as the centre of Strumica Diocese for a short period of time was named Tiberiopolis – a name which was used mostly by the Byzantine administration and the church tradition. The town is connected with the cult of the Holy Fifteen of Tiberiopolis, who suffered for Christ during the reign of the emperor Julian the Apostate, by the end of the 4th century. Their hagiographies were written by the archbishop Theophylactus of Ohrid. Of the great veneration of these saints speaks also the fact that Strumica bishops were for some time called "Tiberiopolitan bishops", as well as the discovered foundations of the early-Christian basilica of the Holy Fifteen in Strumica.
In the 9th century, the Patriarchate of Constantinople revived its mission in Macedonia, through the holy brothers Methodius and Cyril. This was also the aim of the mission of
Saint Methodius of Thessalonica, who, being a Constantinopolitan royal regent from 845 to 855, was the governor in this region. The hagiography of Methodius states
that together with his brother Cyril, who visited him, they spread Christianity
along the river Bregalnica as well. Saint Cyril baptised thousands of Macedonians
then, which is also known from the oral tradition. It says in one of them that
St. Methodius during whole ten years preached to the Macedonians the Word of God
along the flow of the river Bela Reka – which flows east of the village of
Veljusa, passes through the village of Vodoca and in the lower course takes
the name Vodocnica – and the monastery of Vodoca is said to have been the nursery-garden
of enlightenment and monasticism. It is assumed with great certainty that in
this monastery, almost until one thousand years ago, church books were translated
from Greek into the Macedonian language. As a disciple of Sts. Methodius and Cyril,
Saint Clement of Ohrid also had strong influence in this region, for according
to tradition, he came from Strumica. In the list of bishops from this period,
the name Clement is written as a bishop of Tiberiopolis.
During the Constantinopolitan rule in 11th and 12th centuries, Strumica Diocese, being part of the Ohrid Archdiocese, was together with it under the Patriarchate of Constantinople. At that time most estates from the Strumica region, including the monastery church in the village of Veljusa, were granted to the title: of the Holy Mountain (Mt Athos) Hagiorite monastery of Iveron. Strumica metropolis became a part of the Ohrid Archdiocese until its abolishment in 1767. Metropolitan Ananius contributed to its abolishment by supporting the Patriarchate of Constantinople in the conflict between the two Churches.
Towards the end of the 18th and the beginning of the 19th
century, Strumica was at the same time the residence of a Greek bishop, a Turkish
regent, and from 1897 it was the residence of a Bulgarian metropolitan as well.
The influence by the Patriarchate of Constantinople began to decline, as opposed
to the enhanced propaganda and expansion on the part of the Bulgarian Exarchy,
especially after 1897, when the Bulgarian
bishop Gerasimus was appointed in Strumica.
At the beginning of the 20th century, Strumica took part in the Balkan wars and in World War I. Macedonian, Greek, Serb, and Bulgarian interests clashed. The city of Strumica and some of the villages were set on fire. The monastery in the village of Veljusa was also set on fire and the monastery quarters and partly the church were burned down.
Until World War II, the Diocese of Strumica was within the Zletovo and Strumica Diocese of the Serbian Orthodox Church. After the Ohrid Archdiocese was re-established as The Macedonian Orthodox Church in 1958, Zletovo and Strumica Diocese became again part of it. In 1988, by the resolution of the Holy Synod of the Macedonian Orthodox Church, the Diocese of Strumica was re-established, later on to include the towns of Radoviš and Valandovo. Today, Strumica diocese spreads on the territory of the municipalities of Strumica, Berovo, Pehcevo and Dojran.
In 1995, the monk Nahum, who came from the monastery Gregoriou on Mount Athos, was enthroned the bishop of Strumica. With his ordination the entire spiritual life in the diocese was renewed, particularly the monastic life.