Христијанството во Македонија почнало да се проповеда уште во апостолско време. По своето обраќање во христијанството, светиот апостол Павле станал најупорниот и најзабележителниот проповедник на новото месијанско учење, ширејќи го Евангелието на распнатиот и воскреснатиот Христос насекаде во тогаш развиениот и цивилизиран свет.
Апостол Павле, за време на својата мисионерска дејност, спровел повеќе мисионерски и благовеснички патувања, во текот на коишто тој го проповедал Христовото Слово и на Евреите, но и на паганите. Апостол Павле е веројатно првиот од апостолите кој во неговата вистинска суштина ја сфатил флексибилноста на Евангелието и на Христовите поуки и зборови. Тој сфатил дека Христос не дошол и не бил испратен од Својот Отец само за избраниот израелски народ, туку дошол за на сите народи и на сите луѓе да им даде шанса да се избават од смртта и да ги достигнат портите на Царството небесно. Така, апостол Павле организирал бројни нови христијански општини, трудејќи се со сите свои физички, психички и интелектуални сили овие општини правилно да ги насади, втемели и утврди во веќе применото христијанско учење. Апостол Павле напишал бројни Посланици до овие црковни општини во кои, слободно можеме да кажеме, е вткаена целата христијанска теологија и е поставен темелот на сиот христијански морал и подвижништво. Повеќето од овие Посланици се влезени во Новозаветниот канон на Светото Писмо, а со текот на времето некои од нив биле загубени.
Инаку, Своето прво патување надвор од Азија, светиот апостол Павле го направил токму во Македонија. Тоа започнало во 51 година, а завршило во 54 година, при што во текот на тие години апостолот Павле посетил и некои грчки градови, каде што, исто така, биле основани христијански црковни општини. На тие негови патувања го придружувале и апостолите Лука, Тимотеј, Сила и Тихик, кои и самите, независно од светиот апостол Павле, работеле на христијанизација на народот на овие простори. Низ Македонија проповедал и светиот апостол Андреј Првоповикан, кој го поставил светиот апостол Урбан за прв епископ во Македонија. Светиот апостол Силуан бил првиот епископ во Солун, а Епафродит во Адрија или Адријакија (погранично место со Тракија). Што значи дека уште тогаш се поставени темелите на организирана Црква во Македонија. Би спомнале тука и дека апостолите Аристарх и Секунд биле Солунјани, Епафродит бил од Филипи, а Гај од Добер (Дервија) кој најверојатно се наоѓал накаде меѓу Струмица и Валандово. Во тоа време Македонија била под римска власт така што често ги менувала своите граници и својот етнички состав. Во новозаветната книга, напишана од Светиот апостол Лука „Дела на светите апостоли“ се вели дека кога апостол Павле се наоѓал во Троада, му се јавил на сон „еден Македонец“, кој го молел велејќи: „Премини во Македонија и помогни ни!“ (Дела Ап. 16, 9). Народот кој пред неколку векови, штитејќи ја Европа се кренал против Азија и со силата на своето оружје истата ја покорил, сега самиот го повикува светиот апостол Павле, за да ја донесе во Македонија добрата вест што се родила во Азија, и апостолот Павле веднаш се одзвал на македонскиот повик. Уште истиот ден тој и неговите сопатници и блиски соработници, кои, како што спомнавме, го придружувале при неговите мисионерски патувања – Сила, Тимотеј и Лука, отпловиле во градот Филипи (Дела Ап. 16, 11-12), кој се наоѓал на 15 километри од брегот на Егејското Море.
Градот Филипи бил средиште на жива културна, религиозна и трговска дејност. Низ него поминувале сите поважни патишта што го пресекувале Балканскиот Полуостров. Градот Филипи е познат по тоа што е обновен од големиот македонски цар Филип и тој самиот е сведок на настаните поврзани со паѓањето на Римската република (во 42 година пред Рождеството Христово) и е првиот град во Европа, каде што било проповедано и прифатено христијанството.
Уште со самото пристигнување во Филипи, светиот апостол Павле и неговите сопатници започнале да го проповедат христијанството. Слушателите на апостолот Павле пред сè биле Македонци, а тоа може да се заклучи од Посланието на светиот апостол Павле до Филипјаните, каде се вели дека во Филипи имало многу мал број Евреи и Грци.
Потоа, откако го оставил во Филипи светиот апостол и евангелист Лука, светиот апостол Павле со Сила и Тимотеј заминале за Солун (Дела Ап., 17 глава), главниот град на Македонија.
Од историјата е познато дека во солунското пристаниште, македонските цареви ги чувале бродовите на својата флота. Солун, во времето на апостолите, исто така бил значаен трговски, административен и културен центар. Тука се среќавале трговци од Блискиот Исток и Мала Азија со трговци од Балканот и Европа. За разлика од Филипи, во Солун постоела бројна еврејска колонија: тука имало и еврејска синагога, во која апостол Павле, за време на својот престој во Солун, го проповедал христијанството. Исто така имало и бројна колонија на Грци, од кои покрај далеку побројното етничко македонско население што го примале Словото Христово, истото го прифаќале и некои од нив (Дела Ап. 17, 4).
Од Солун, апостолите Павле, Сила и Тимотеј заминале за Бер, град кој бил значително помал од Солун: имало пристаниште, силно развиена трговија, а неговите жители во главно биле Македонци.
Апостол Павле покажувал огромна грижа и љубов кон Македонците, за што честопати и пишува во своите посланија. За оваа љубов на апостол Павле кон Македопнците зборува и свети Јован Златоуст. Зборувајќи за односот на апостолот Павле кон Македонците, св. Јован вели: „О, каква нежна љубов имал тој кон Македонија и Македонците…!“ Понатаму, гледаме дека големиот христијански проповедник св. Јован Златоуст (IV – V век) за да ги поткрепи своите мисли за љубовта на апостол Павле кон Македонија, ги цитира неговите зборови упатени кон Солунјаните, а тоа значи дека св. Јован Златоуст тесно го поврзува односот на Солун кон Македонија, како и Солунјаните кон Македонците.
Во постапостолскиот период Македонија и македонските црковни општини се посетени од апостолскиот маж Св. Игнатиј Богоносец, кој одејќи на пат за Рим, каде требало да биде суден и погубен, насекаде се среќавал во сите градови со христијаните и ги утврдувал во верата. Патот Via ignatia, кој името го добил токму во негова чест, поминува директно низ Македонија, па логично е да заклучиме дека овој голем и значаен светител, кој во голема мера ја искристализирал христијанската теологија, се сретнал и со Македонците и им пружил полезни и значајни поуки за христијанскиот живот.
Христијанска македонска црква за време на гоненијата на христијаните во првите три века дала голем број маченици, кои и ден денес се незаменливи светила и длабоко се врежани во колективното сеќавање на македонскиот народ. Најпознат маченик од тој период секако е св. Димитриј Солунски, кој со неговото големо дело, со неговото смирение, незлобивост и несреброљубивост е незаменливо светило во воспитувањето на сите генерации Македонци. Неговиот култ и ден денес е особено развиен меѓу македонското православно неселение.
Како резултат на христијанизацијата извршена во првите три века, веќе на почетокот на IV век христијаните на просторот на Македонија имале организирана Црква со црковна ерархија, чии епископи понатаму редовно учествувале на помесните и вселенските Собори.
Во Македонија христијанството, како впрочем и во целото тогашно Римско царство, почнало посебно да зема замав кога римскиот цар Костантин Велики во 313 година го прекинал прогонството на Христовата црква и со указ им дал можност на христијаните слободно да ја исповедаат и да ја проповедаат својата вера. Во Македонија од тоа време се познати епископските седишта во Солун, Стоби, Скупи, Астибо и Хераклеа. Кон крајот на V век Солун веќе е седиште на Архиепископија, а Скупи на митрополија.
На почетокот од VI век Македонската црква веќе била силно утврдена и во тој период во Македонија, во селото Таор, покрај Скопје се родил големиот римски император Јустинијан I (527-565), кој е составувач на познатото Римско право и кој дал значен придонес во литургиската и архитектонската христијанска наука. Општо е познато дека Јустинијан врз основа на своето лично подвижничко искуство интензивно работел на литургиски и теолошки текстови и дека за негово време е подигната и изградена можеби најубавата и најголемата христијанска црква во православието – Света Софија во Цариград. Дека Јустинијан бил тесно поврзан со своите корени и дека бил национално свесен за своето потекло доказ е и издигнувањето на Македонската црква во ранг на Архиепископија под име Јустинијана Прима, која самиот тој ја вброил да биде трета по чест, веднаш после големите и древни христијански центри Рим и Цариград. Скупскиот митрополит Кателијан бил издигнат на ниво на автокефален Архиепископ и тој бил првиот Архиепископ на Архиепископијата Јустинијана Прима.
Како поглавари на Архиепископијата Јустинијана Прима историјата ги бележи и Бененат, Павле, Јован I, Леон, и Јован IX, кој во 680-681 година учествувал на Трулскиот Собор во Цариград.
Во пероидот до IX век настануваат некои етнички промени во Македонија, Македонците се вовлечени во повеќе војни и одбрана на својата територија, а со слабеењето на економскиот и социјалниот статус на населението, политичкото и црковното влијание од Цариград се повеќе се наметнувало. Етничките промени и војните придонеле да ослабне и христијанското организирање во овие простори.
