To Γυμνάσιο Αποστόλου Παύλου είναι ένα από τα πολυπληθέστερα Γυμνάσια όχι μόνο της Πάφου αλλά και Παγκύπρια. Βρίσκεται κοντά στην εκκλησία Αποστόλου Παύλου και Πέτρου (από όπου πήρε και το όνομά του).
Ιδρύθηκε το 1995 και τα επίσημα εγκαίνιά του έγιναν στις 21 Νοεμβρίου 1997 από τον πρώην Πρόεδρο της Κυπριακής Δημοκρατίας κ. Γλαύκο Κληρίδη. Την πρώτη χρονιά λειτουργίας του φοίτησαν 273 μαθητές (154 μαθητές και 119 μαθήτριες), που κατανεμήθηκαν σε οκτώ τμήματα της Α΄ τάξης και της Β΄ τάξης. Δίδαξαν 25 καθηγητές, δύο Βοηθοί Διευθυντές και η Διευθύντρια.
Αρχικά τα τμήματα της Β΄ τάξης στεγάζονταν σε αίθουσες του Λυκείου Αγίου Νεοφύτου, επειδή δεν είχε αποπερατωθεί η πρώτη φάση του έργου. Η δεύτερη φάση του σχολικού κτιρίου ολοκληρώθηκε το Σεπτέμβρη του 1996 με την ανέγερση αίθουσας πολλαπλής χρήσης, τη διαμόρφωση της εισόδου του σχολείου και την κατασκευή χώρου στάθμευσης.
Λειτουργούν σήμερα στο σχολείο εργαστήρια των ειδικοτήτων Οικιακής Οικονομίας, Φυσικής, Χημείας-Βιολογίας, Τεχνολογίας, Πληροφορικής, Τέχνης και Μουσικής, το Γραφείο Συμβουλευτικής και Επαγγελματικής Αγωγής και η Βιβλιοθήκη.
Το Γυμνάσιο Αποστόλου Παύλου στη πορεία του έχει επιδείξει πλούσια πνευματική, καλλιτεχνική και πολιτιστική δραστηριότητα με διακρίσεις σε Παγκύπρια κλίμακα. Σ΄αυτό συνέβαλαν όλοι οι παράγοντες, Σχολική Εφορεία, Σύνδεσμος Γονέων, Μαθητές, Καθηγητές και Διεύθυνση του Σχολείου.
