Ο βυζαντινός ναός του Αγίου Παύλου, βρίσκεται ανατολικά της Αγίας Ρούμελης σε απόσταση 30 λεπτών περίπου (διαδρομή Ε4) με τα πόδια. Χτίστηκε κατά τον 11ο αι. μ.Χ. δίπλα στη θάλασσα, στη θέση που κατά την παράδοση αποβιβάστηκε στη ξηρά ο Απόστολος Παύλος κατά το ταξίδι του προς τη Ρώμη.
Πρόκειται για μικρό σταυροειδή ναό με τρούλο, κατάγραφο με τοιχογραφίες, οι οποίες όμως δυστυχώς δεν διατηρούνται σήμερα σε καλή κατάσταση.
Στο ναό ο επισκέπτης μπορεί να φτάσει είτε με τα πόδια, μέσω του Ε4, από την Αγία Ρούμελη, είτε με καραβάκι από εκεί.
Ιδρυτής του θεωρείται ο Κρητικός Άγιος Ιωάννης ο Ξένος, ο οποίος έδρασε στο νησί κατά τη δεύτερη βυζαντινή περίοδο και μετά την απελευθέρωση του νησιού από τους Άραβες. Ίδρυσε πολλούς ναούς και μοναστήρια και αναζωογόνησε την ορθόδοξη συνείδηση του ντόπιου πληθυσμού.
