Barnabas'la yaptığı ilk Haber gezisinde Pavlus Samandağı'ndan (Selefke'den) gemiyle Barnabas'ın memleketi olan Kıbrıs'a gitti (Res.İş. 13:4). Salamis'ten "Pafos'a kadar tüm adayı baştan başa aştılar" (Res.İş.13:6). Orada onları yanına çağıran ve Tanrı'nın Sözü'nü dinlemek isteyen vali Sergius Pavlus'la konuşurken Yahudiler'in yalancı bir peygamberi ve büyücü olan Elimas'la karşılaştılar. Kutsal Ruh'uh gücüyle bu adamın karşı koymasını yendiler. Vali de iman etti (Res.İş. 13:6-12). Sonra "Pafos'tan denize açılıp Pamfilya'nın Perge kentine geldiler" (Res.İş. 13:13). Adada iki Pafos vardı. Eski Pafos Finikeliler'in çok öncelerden kurmuş ve deniz kıyısında bulunmayan kentti. Yeni Pafos Romalılar'ın adayı M.Ö. 58 yılında ele geçirince deniz kıyısında kurdukları yönetim merkeziydi. Barnabas'la Pavlus valiyi Yeni Pafos'ta ziyaret etti. Bugünkü Baf.