A primeira viagem missionária de Paulo (46-48 dC) foi a mais curta, no tempo e distância, mas foi, no entanto, um avanço muito significativo na história da nova igreja cristã. Estabeleceu Paulo como líder na divulgação da Palavra de Deus. Ele passou a escrever uma grande parte do Novo Testamento que temos hoje. A jornada começou de Seleucia, o porto de Antioquia (Atos 13:1-4). (Note-se que havia 2 cidades com o nome de Antioquia - Antioquia da Síria, o seu ponto de partida, e uma na Turquia). Paulo (então ainda chamado de Saulo), Barnabé e Marcos navegaram para Chipre, cerca de 80 milhas (130 quilómetros) ao sul-oeste. Neste momento, Barnabé era ainda o membro sénior sobre Paul, que era um amigo íntimo depois da sua conversão a caminho de Damasco. Isto mudaria em breve. Após o desembarque em Salamina, e proclamar a Palavra de Deus nas sinagogas (Atos 13:5), eles viajaram ao longo de toda a costa sul da ilha de Chipre, até que chegaram a Pafos (Atos 13:6). Lá, Sérgio Paulo, o procônsul romano, foi convertido depois que Paulo repreendeu o malvado feiticeiro Elimas (At 13:6-12). Foi por esta altura que Paul se tornou efectivamente o líder. Foi a partir de então chamado Paul, em vez do seu antigo nome, Saulo.