Mae’n amlwg fod Paul a Titus wedi bod ar Ynys Creta gyda’i gilydd rywbryd ar ôl i Paul gael ei ryddhau o’r ddalfa yn Rhufain (gw. Actau 28:16,30-31). Mae lle i gredu fod Paul wedi cael ei ryddhau ar ôl iddo ymddangos o flaen yr uchel-lys yn Rhufain, a’i fod wedi mynd ar bedwaredd daith genhadol.

Mae llenyddiaeth Gristnogol gynnar yn dweud fod Paul wedi mynd â’r efengyl i Sbaen, a rydyn ni’n gwybod ei fod wedi bwriadu gwneud hynny (Rhufeiniaid 15:24,28). Yn ei lythyrau at Timotheus a Titus mae sôn amdano yn ymweld ag Ynys Creta (Titus 1:5), Nicopolis (Titus 3:12) a Miletus (2 Timotheus 4:20) yn ogystal ag Effesus a Macedonia (Philipi mae’n debyg).