Ο Άγιος Παύλος βρίσκεται στη γεωγραφική περιοχή της Πιτσιλιάς, στη νότια πλευρά της Παπούτσας.[13] Είναι κτισμένος σε υψόμετρο 670 μέτρων πάνω από την επιφάνεια της θάλασσας.[14] Βόρεια συνορεύει με τον Άγιο Θεόδωρο, ανατολικά με τον Άγιο Κωνσταντίνο και νότια και δυτικά με το Καλό Χωριό.
Το τοπίο της περιοχής είναι τραχύ και πετρώδες, με απότομος πλαγιές και πολλές κοιλάδες.[15] Στο φυσικό περιβάλλον της περιοχής περιλαμβάνονται καρυδιές, πλατάνια, αμπέλια, ελιές και χαρουπιές.[13]
Σύμφωνα με την παράδοση, ο Απόστολος Παύλος μαζί με τον Απόστολο Βαρνάβα και τον Απόστολο Μάρκο και τη συνοδεία τους, κατά την πρώτη περιοδεία τους στην Κύπρο για τη διάδοση του Χριστιανισμού το 45 μ.Χ. έφτασαν στην περιοχή του χωριού. Εκεί θεράπευσαν μια τυφλή κοπέλα που συνάντησαν στον ποταμό. Η παράδοση αναφέρει ότι ο Άγιος Παύλος έκανε διευθετήσεις με τις οποίες κτίστηκαν σπίτια και δημιουργήθηκε το χωριό. Για τον λόγο αυτό το χωριό ονομάστηκε Άγιος Παύλος.[16]
Τα χαλάσματα και τα διάφορα ευρήματα που εντοπίστηκαν στην περιοχή μαρτυρούν ότι αρχικά δημιουργήθηκαν οικισμοί βορειότερα του σημερινού χωριού. Συγκεκριμένα οικισμοί φαίνεται να υπήρχαν στις τοποθεσίες Στύρακας, Κλειδωρένατα, Πλάτη, Λινούες, Καλίτσα και Μαρούδες. Με τα χρόνια οι οικισμοί αυτοί ενώθηκαν και ονομάστηκαν Κάμπος. Ανατολικά του χωριού υπήρχε και ο αρχαίος οικισμός Ζήλος, που είναι πιθανόν να είχε κατοικηθεί αρχικά από αποίκους από τη Μικρά Ασία (η Ζήλα ήταν πόλη της Μικράς Ασίας στα νότια της Αμάσειας).[13]
Όταν ανακαλύφθηκε ο χαλκός άρχισε η εξόρυξή του από την περιοχή Κλειδωρένατα, στην τοποθεσία Πέτρα του Ρκου. Εκεί ανεβρέθηκαν νομίσματα της εποχής των Πτολεμαίων και αρχαίοι τάφοι. Ακολούθησε η κάθοδος των Αχαιών στην Κύπρο και ο εποικισμός του νησιού από αυτούς. Τότε άρχισε η εμπορική εκμετάλλευση του χαλκού. Αυτό οδήγησε στην ανάπτυξη των οικισμών της περιοχής. Ενδεικτικά, οι οικισμοί Καλίστα και Μαρούδες αναφέρονται στην απογραφή του 1565. Δεν αναφέρονται στην απογραφή του 1825 γιατί είχαν ήδη εγκαταλειφθεί.[13] Οι κάτοικοί τους μετακινήθηκαν είτε στον Άγιο Παύλο είτε στον Άγιο Θεόδωρο.
Σύμφωνα με τις απογραφές πληθυσμού που πραγματοποιήθηκαν στην Κύπρο, ο πληθυσμός του χωριού έφτασε στο αποκορύφωμά του το 1960. Στη συνέχεια ο πληθυσμός ξεκίνησε να μειώνεται, αλλά μέχρι και το 1982 η μείωση ήταν μικρή. Τις επόμενες δεκαετίες ακολούθησε σημαντική μείωση του πληθυσμού λόγω αστυφιλίας.[13] Ο πίνακας που ακολουθεί παρουσιάζει τον πληθυσμό του Αγίου Παύλου όπως καταγράφηκε στις απογραφές πληθυσμού που έγιναν στην Κύπρο.