Своето прво патување надвор од Азија, светиот апостол Павле го направил во Македонија. Започнало во 51 година а завршило во 54 година, при што апостолот Павле посетил многу градови, каде основал христијански црковни општини.

Според Библијата во ,, Дела апостолски ,, кога апостолот Павле се наоѓал во Троада, му се јавил насон ,, еден Македонец ,, кој  го молел :,, Премини во Македонија и помогни ни !,, (Д.А. 16,9).

Народот кој пред неколку векови, покорил три континенти по Европа Азија и Африка со силата на своето оружје, сега го повикува апостолот Павле, за да ја донесе во Македонија големата благавест што се родила во Азија.

 Апостолот Павле веднаш се одзвал на македонскиот повик, уште дента тој и неговите соработници, кои го придружувале - Сила, Тимотеј и Лука, отпловиле за Македонија во Филипи (Д. А. 16.11-12), град на 15 километри од брегот на Егејското Море.

Слушателите на апостолот Павле биле Македонци, а тоа може да се заклучи од Посланието на Светиот апостол Павле до Филипјаните, каде се вели дека во Филипи имало многу мал број Евреи и Грци а по честото спомнување на Македонците уште и за време на пловидбата.
Потоа откако го оставил во Филипи светиот апостол и евангелист Лука, светиот апостол Павле со Сила и Тимотеј заминале за Солун (Д. А. 17 гл), главниот град на Македонија.

Имало бројна колонија на грци, од кои покрај Македонците што го примале Словото Христово, го прифаќале и некои грци (Д.А. 17.4,).

Светиот Јован Златоуст зборувајќи за односот на Ап. Павле кон Македонците, вели: ,, О, каква нежна љубов имал тој кон Македонија и Македонците. . .!,,

 Понатаму, пак, гледаме дека големиот христијански проповедник Св.Јован Златоуст (IV-V век) за да ги поткрепи своите мисли за љубовта на апостолот Павле кон Македонија, ги цитира и зборовите на апостолот упатени кон Солунјаните, а тоа значи дека Св.Јован Златоуст тесно го поврзува односот на Солун и Македонија, и солунјаните како Македонци.
Во Македонија христијанството почнало зема замав кога  Костантин Велики во 313 година го прифатил за државна религија и овозможил христијаните слободно да ја исповедаат и  проповедаат својата вера. Од тоа време се познати епископските седишта во Солун, Стоби, Скупи, Астибо и Хераклеа. Кон крајот на V век Солун веќе е седиште на Архиепископија, а Скупи на митрополија. По почетокот на V век, поради наметнувањето на непознатиот грчки јазик, возвишените вистини на христијанското учење и мистичките длабочини на црковните богослужби останале не достапни за нив, па затоа и нивното христијанизирање останало површно и недостапно.