Samothraki Havari Pavlos’un Avrupa topraklarında ziyaret ettiği ilk yerdi. Havari Pavlos’un kilise sırası Samothraki’nin kuzey tarafında, Kamariotisa – Thermes Loutra yolunun 7. km’sindedir. Havari Pavlos’un M.s. 49 yılında adadan geçişini canlandıran dört büyük karo mozaikle süslenmiş ve Samothraki yapı sanatıyla ve geleneğiyle inşa edilmiş, yarım daire şeklinde bir dizi sütundan ve oluşmaktadır. Tam ortasında birçok dile tercüme edilmiş olarak olayı tanıklık eden Havari ayetleri bulunmaktadır (16, 9-12). Yazılan ve söylenenlere göre Havari Pavlos, Troada’da bulunduğu zaman, kendisine Asya’yı bırakıp Avrupa’ya geçerek İncil’i Yunanistan’a duyurmaya davet eden bir adam gördüğü bir hayal görmüş. O zaman Pavlos, Troada’dan Samothraki’ye geçmek üzere bir gemiye binmiş, adada(büyük ihtimalle Paliapolis Limanı’nda) inmiş, yerli Samothrakililerle karşılaşmış, bir gün onlarla kalıp gece orada yatmış ve ertesi gün Neapoli’ye (Kavala) gitmek üzere ayrılmış.