According to the sources in the Acts, Saint Paul, Christ's disciple, began spreading Christianity in Macedonia and elsewhere on the Balkan Peninsula towards the mid 1st century AD. He visited this region on two occasions during his journeys through Europe and Asia. He was followed by Timothy and Silas, who remained in Macedonia after his departure. At that time, as a Roman province Macedonia often changed its borders and its ethnic composition. As a result of the Christianization in the first three centuries, the Christians in Macedonia at the beginning of the 4th century already had an organised Church with an established ecclesiastical hierarchy, whose bishops regularly participated at the ecumenical councils.
In the 5th century the Church had several metropolises and dioceses. The metropolises of Thessalonica and Skopje were the most distinguished among them. Several Christian basilicas originate from this period, including the one near the village of Bardovci, in the western outskirts of Skopje.
During the reign of the emperor Justinian I (527-565), who came from the village of Tauresium in the Skopje region, a new town was built near the emperor's birthplace, named Justiniana Prima after him. The Metropolitan of Skopje was appointed an autocephalous Archbishop. Cathellian was the first Archbishop of the Archdiocese Justiniana Prima, at the time the third by honour among the local Orthodox Churches, after Rome and Constantinople. The other archbishops were: Benenat, Paul, John I, Leon and the last one John IX, who in 680-81 took part at the Trullo Council in Constantinople.
The work of the holy Apostle Paul and the holy emperor Justinian I was continued by the holy brothers Methodius and Cyril and their disciples Saints Clement and Nahum of Ohrid. In the second half of the 10th century, within the borders of Samuel's state, the autocephalous Ohrid Archdiocese was established with the rank of patriarchate, on the foundations of Justiniana Prima. After the fall of Samuel's state, the Ohrid Archdiocese was reduced to a lower rank of church hierarchy (archbishopric) and it existed as such for eight centuries, until its abolishment in 1767 by the Turkish sultan Mustapha III, and its dioceses were annexed to the Patriarchate of Constantinople. From this moment on Macedonian people made all possible efforts to restore the Archdiocese. Its dioceses were under several jurisdictions of the neighbouring Orthodox Churches and this struggle became particularly fierce in the second part of the 19th and the first part of the 20th century. Convenient conditions for restoration of the independence were created not earlier than during World War II (1941-1945). Right before the end of the war, in 1944, in the village of Gorno Vranovci, an Initiative Board for Organisation of the Macedonian Orthodox Church was formed. In March, 1945, in Skopje, a Resolution to restore the Archdiocese of Ohrid as Macedonian Orthodox Church was made at the First Clergy and Laity Assembly. This decision was submitted to the Holy Synod of the Serbian Orthodox Church, since before World War II several dioceses in Macedonia were under the United Orthodox Church of Serbs, Croats and Slovenians, known later as Serbian Orthodox Church. The Synod of the Serbian Orthodox Church did not accept this decision, which resulted in the following actions of the Initiative Board: instead of as an autocephalous, the Board insisted on the Church being recognised as autonomous. This request was also rejected. In 1958, the Second Clergy and Laity Assembly was held in Ohrid and the proposal for restoration of the Ohrid Archdiocese of Saint Clement as a Macedonian Orthodox Church was accepted and Dositheus was appointed the first archbishop.
The Holy Synod of the Serbian Orthodox Church agreed with the decisions of the Macedonian Clergy and Laity Assembly in the resolution AS. No 47/1959 and 6/1959, minutes 57 of June 17/4, 1959.
As a sign of agreement, a Liturgy was concelebrated with the Serbian Patriarch German, on July 19, 1959, in Skopje, in the church of Saint Menas. At the same time, Clement was ordained the bishop of Prespa and Bitola. This meant that the Holy Synod of the Serbian Orthodox Church gave autonomy to the Macedonian Orthodox Church, which remained in canonical unity with the Serbian Church under their Patriarch. Few days later, in the church of St. Nicholas in Štip, H.E. Nahum was ordained the bishop of the diocese of Zletovo and Strumica. The Holy Synod of the Macedonian Orthodox Church was established together with other administrative bodies in the Archdiocese and the dioceses in conformity with the Constitution of the Macedonian Orthodox Church. In May, 1962, accompanied by Patriarch German and other representatives of the Serbian Orthodox Church, Patriarch Alexis of Moscow visited the Macedonian Orthodox Church. Among them were Metropolitan Nicodemus, Bishop Pimen and other dignitaries of the Russian Orthodox Church. On the feast of Saints Methodius and Cyril, in the church of the Holy Mother of God Kamenska, in Ohrid, Patriarch Alexis of Moscow, Patriarch German and the Macedonian Metropolitan Dositheus concelebrated Holy Liturgy. It was the first Holy Liturgy to be concelebrated by the head of the Macedonian Orthodox Church with heads of other autocephalous Orthodox Churches.
In 1966 the relations with the Serbian Church got worse again. Due to the conflicts and misunderstandings, the Holy Synod of the Macedonian Orthodox Church summoned the Third Clergy and Laity Assembly on July 17, 1967, in Ohrid. At the formal session in the Ohrid church of St. Clement, the Holy Synod proclaimed the Macedonian Orthodox Church as AUTOCEPHALOUS. The act of proclamation was made by the Holy Synod of the Macedonian Orthodox Church during the Holy Liturgy celebrated in the church of St. Clement of Ohrid on July 19, 1967, or exactly on the second centennial after it had been banned by the Ottoman authorities.
The jurisdiction of the Macedonian Orthodox Church spreads not only throughout Macedonia, but also in the church communities abroad.
According to Article 17 from the Proclamation of Autocephaly, the Macedonian Orthodox Church as an administrative part of the One, Holy, Catholic and Apostolic Church is to observe the Holy Scriptures and the Holy tradition, the Canons of the Apostles and the decrees of the ecumenical councils and is to follow them and the Constitution of the Macedonian Orthodox Church.
Praying humbly for the other ones, the Macedonian Orthodox Church will always rely on the prayers, blessings and assistance of the elder sibling holy local Orthodox Churches.