Μέχρι το 1959 μοναδικό σχολείο Μέσης Εκπαίδευσης ήταν το Παγκύπριο Γυμνάσιο. Από τη σχολική χρονιά 1959-1960, ξεκίνησε τη λειτουργία του και το Παγκύπριο Σχολείο Θηλέων Παλουριωτίσσης, το σημερινό Γυμνάσιο Παλουριώτισσας, ως παράρτημα του Παγκυπρίου, με επικεφαλής Βοηθό Διευθυντή. Την επόμενη χρονιά λειτούργησε το Παγκύπριο Γυμνάσιο Θηλέων Παλουριωτίσσης με αυτοτέλεια ως εξατάξιο Γυμνάσιο. Το νέο σχολείο στεγάστηκε σε ιδιόκτητο κτήριο, σε γη που παραχωρήθηκε από την εκκλησιαστική επιτροπή της Παναγίας της Παλουριώτισσας.
Δύσκολη περίοδος για το σχολείο ήταν η χρονιά 1963-1964, όταν το σχολείο βρέθηκε στο επίκεντρο των διακοινοτικών συγκρούσεων. Για δεύτερη φορά δοκιμάστηκε το 1974, οπότε πάλι έγινε στόχος επίθεσης από τους Τούρκους και οχυρό αντίστασης κατά των εισβολέων. Τη σχολική χρονιά 1974-1975 μεταφέρθηκε προσωρινά στο κτήριο του Παγκυπρίου Γυμνασίου και λειτουργούσε με απογευματινή φοίτηση. Επέστρεψε στο δικό του κτήριο το 1975-1976, τμήματα όμως του σχολικού χώρου, συμπεριλαμβανομένου και του γηπέδου, εξακολουθούσαν να χρησιμοποιούνται ως φυλάκια ή να ανήκουν στη λεγόμενη νεκρή ζώνη. Ολόκληρο το σχολικό κτήριο επανήλθε στη δικαιοδοσία του σχολείου από το 1977-1978, αν και τμήμα της αυλής και το γήπεδο του σχολείου συνέχισαν να θεωρούνται «νεκρή ζώνη».
Από την πρώτη ημέρα της λειτουργίας του φοιτούσαν στο σχολείο μόνο κορίτσια, μέχρι το 1979-1980, περίοδο κατά την οποία έγινε μικτό. Από το 1980-1981 τη θέση του εξατάξιου Γυμνασίου πήραν το Γυμνάσιο και Λύκειο Παλουριώτισσας.
Για τη στέγαση των μαθητών του Γυμνασίου χρησιμοποιήθηκε το κτήριο που κτίστηκε στην ίδια αυλή, για να φιλοξενήσει τους προσφυγοποιημένους, μετά το 1974, μαθητές του Δημοτικού Αγίου Κασσιανού. Πολλές αίθουσες διδασκαλίας,ωστόσο, στεγάζονται ακόμα στο κτήριο του Λυκείου.
Στις 30 Απριλίου 2006 πραγματοποιήθηκε η τελετή αδελφοποίησης του Γυμνασίου Παλουριώτισσας με το Γυμνάσιο Κολλεγίου Αθηνών.
Ονομασία του Σχολείου
Πρώτη ονομασία του σχολείου ήταν Παγκύπριον Γυμνάσιον Θηλέων Παλουριωτίσσης, από το 1960 ως το 1975. Κατά το χρονικό διάστημα 1975-1979 το σχολείο ονομαζόταν Γυμνάσιον Παλουριώτισσας. Την ονομασία αυτή διατήρησαν οι δυο κύκλοι, Λυκειακός και Γυμνασιακός, έως το 1987. Από το σχολικό έτος 1987-1988 το Γυμνάσιο κράτησε τον τίτλο Γυμνάσιο Παλουριώτισσας και το Λύκειο πήρε την ονομασία Λύκειο Παλουριώτισσας.
Διευθυντές του Γυμνασίου Παλουριώτισσας
| Εξατάξιο: | |
| Καλλιόπη Καραγιώργη | 1961-1967 |
| Μάγδα Κιτρομηλίδου | 1967-1980 |
| Τριτάξιο: | |
| Χρίστος Αρτεμίου | 1980-1981 |
| Αντρέας Παπαβασιλείου-Λουκάς Κακουλλής | 1981-1982 |
| Λουκάς Κακουλλής | 1982-1987 |
| Αντρέας Παναγή | 1987-1990 |
| Ελλάδιος Χανδριώτης | 1990-1991 |
| Ελλάδιος Χανδριώτης-Αντρέας Φωτίου | 1991-1992 |
| Αντρέας Φωτίου | 1992-1994 |
| Αντώνης Λίγγης | 1994-1995 |
| Στέλιος Παπαντωνίου | 1995-1996 |
| Κυριάκος Κυριάκου | 1996-1997 |
| Φαίδρα Παπακώστα | 1997-2003 |
| Αρτέμης Ευθυβούλου | 2003-2004 |
| Ιάκωβος Ιακώβου-Νίκη Παπαδοπούλου | 2004-2005 |
| Μαρία Θεοδότου | 2005-2009 |
| Έλενα Λειβαδιώτου | 2009-2010 |
| Άριστος Αριστοτέλους | 2010-2011 |
| Δέσποινα Παπαγιάννη | 2011-2014 |
| Δαυίδ Δαυίδ | 2014-2017 |
| Ελένη Παπαστεφάνου | 2017-2019 |
| Δέσποινα Παπαγιάννη | 2019-2022 |
| Χαρά Αναστασίου | 2022- |