Το Δ΄ Γυμνάσιο Πάφου ιδρύθηκε τη Σχολική Χρονιά 1975 - 1976 με στόχο την ικανοποίηση των εκπαιδευτικών αναγκών της επαρχίας Πάφου μετά την Τούρκικη Εισβολή του 1974 στην Κύπρο. Ένα σχολείο με 467 μαθητές αλλά χωρίς δική του στέγη, αυλή και γυμναστήριο.

 

Μέχρι το Δεκέμβρη λειτουργεί ως απογευματινό και στεγάζεται στο Οικονομικό Λύκειο (το σημερινό Νικολαΐδειο Γυμνάσιο) ως τριτάξιο Γυμνάσιο. Στις 7 του Γενάρη του 1976 μετακομίζει στην κάτω πτέρυγα του Τουρκοκυπριακού Σχολείου (αυτή που κατεδαφίστηκε εξαιτίας του σεισμού τον Οκτώβρη του 1996 (6,4 Ρίχτερ).

 

Ο πυρήνας των πρώτων μαθητών ήταν προσφυγόπουλα που κατοικούσαν κυρίως στην περιοχή του Μουττάλου. Πρώτος γυμνασιάρχης που αγκάλιασε με αγάπη και ιδιαίτερο ζήλο το σχολείο ήταν ο κ. Σάββας Χατζηγεωργίου. Στη θέση αυτή υπηρέτησε ως το Μάρτιο του 1983 κατά το οποίο, διορίστηκε μέλος της Εκπαιδευτικής Υπηρεσίας. Μέσα από αντίξοες συνθήκες, όχι μόνο στεγαστικές αλλά και προέλευσης μαθητών, το Δ΄ Γυμνάσιο σταδιακά έγινε εξατάξιο και έδωσε δυναμικά το παρόν του στα εκπαιδευτικά δρώμενα της Πάφου. Το 1978 - 1979 έδωσε τους πρώτους απόφοιτους στην κοινωνία. Από τη Σχολική Χρονιά 1983 - 1984 λειτούργησε και πάλι ως τριτάξιο Γυμνάσιο και το το 1987 μετονομάστηκε σε Γυμνάσιο Α΄ Πάφου.

 

Το Σεπτέμβρη του 2000 μετακόμισε στις νέες εγκαταστάσεις στην περιοχή Λιμνάρκα και μετονομάστηκε σε Γυμνάσιο Α΄ Αγίου Θεοδώρου Πάφου.