Quando as notícias de que um grande profeta operava milagres na Palestina chegaram à ilha, Tito implorou ao seu tio, então governador de Creta, e este arranjou-lhe uma embarcação rumo à Terra Santa. Quando chegou lá, correu em busca do profeta, e finalmente encontrou-o. Era o próprio Senhor, [[Jesus Cristo]], que ensinava nos templos dos judeus e repreendia a corrupção de Seu povo. Tito fascinou-se com sua pregação, e não quis mais voltar a Creta, mas sim segui-Lo por toda a Sua vida.

Quando reencontrou-se com São Paulo na Macedônia, este alegrou-se muito por poder revê-lo, e escreveu a Segunda Epístola aos Coríntios, a qual Tito levou de volta à Acaia. Ao se reencontrarem em Corinto, Tito foi encarregado da coleta de esmolas aos cristãos em Jerusalém. Após retornar do (primeiro) cárcere em Roma, São Paulo partiu a Creta para instruir os cristãos de lá, e pediu para que Tito ficasse na ilha, onde foi feito primeiro Bispo de Creta. Depois, Tito deixou Creta para acompanhá-lo na Dalmácia (atual Sérvia e Albânia), e o santo Apóstolo Artemas tornou-se Bispo de Creta durante os dois anos que São Tito esteve fora.