Η ιστορία της ίδρυσης του σχολείου μοιάζει σαν παραμύθι. Στο χωριό Φοινί της Μαραθάσας γεννιέται ο Αντώνης Θεοδότου, το 1859. Πρώτος του δάσκαλος ο παπάς του χωριού. Εγκαθίσταται στη Λευκωσία. Έχει την τύχη να έχει θείο του τον Αρχιεπίσκοπο Κύπρου Σωφρόνιο, ο οποίος ενδιαφέρεται για τη μόρφωσή του. Τον στέλνει να συνεχίσει τις σπουδές του στην Ευρώπη. Σπουδάζει Ιατρική. Το 1890 εγκαθίσταται στη Λευκωσία, και ασκεί το επάγγελμα του γιατρού. Το 1892, παντρεύεται την Ευγενία Ιωαννίδου Μουμτζή, που άνηκε σε μία από τις πλουσιότερες και γνωστές οικογένειες της Λευκωσίας. Εκλέγεται βουλευτής, διατελεί Δημοτικός Σύμβουλος και Δήμαρχος Λευκωσίας, Επίτροπος και Ταμίας Σχολείων, Πρόεδρος του Διοικητικού Συμβουλίου της Τράπεζας Κύπρου, Πρόεδρος της Επιτροπείας της Εκκλησίας της Φανερωμένης κ.α. Η φήμη του εξαπλώνεται σ’ όλη την Κύπρο, τόσο για την πολιτική του δραστηριότητα, όσο και για τα φιλανθρωπικά και κοινωφελή έργα τα οποία φέρνει σε πέρας με τη βοήθεια της συζύγου του Ευγενίας.
Στη ψυχή τους ήταν χαραγμένα τα λόγια του Άγιου Κοσμά του Αιτωλού: «Καλύτερα αδελφέ μου να έχεις ελληνικό σχολείο εις στην χώρα σου, παρά να έχεις βρύσες και ποτάμια, διότι οι βρύσες ποτίζουν το σώμα, τα σχολεία όμως ποτίζουν την ψυχή. Και ωσάν μάθεις, παιδί μου, γράμματα, τότε λέγεσαι άνθρωπος». Το Φεβρουάριο του 1925 ανακοίνωσαν στην Σχολική Εφορεία Λευκωσίας την απόφασή τους για ανέγερση «Πλήρης Αστική Σχολή». Ο Μιχαήλ Τροκούδης, μετέπειτα Διευθυντής της Αστικής Σχολής Αγίου Αντωνίου, εξαίρει το χαρακτήρα των δύο Ευεργετών λέγοντας: «Η Ευγενία ήταν μορφωμένη σε κυπριωτικά και αθηναϊκά σχολεία, καλλιεργημένη γυναίκα κι ο Αντώνης ένας πονόψυχος και φιλόμουσος άνθρωπος. Ένα αντρόγυνο ταιριαστό με παράδοση χριστιανική και πατριωτική δεν ήταν δυνατό παρά αν συνεχίσουν την ευγενική οικογενειακή αυτή παράδοση και να ωφελήσουν την κοινωνία στην οποία ανήκαν.»
«Επί την υπό των κ.κ. Ν. Χρυσαφίνη και Μ. Σκουφαρίδη δοθείσα πληροφορία ότι οι αξιότιμοι κ.κ. Αντώνιος Θεοδότου και η σύζυγό του Ευγενία ανεκοίνωσαν εις αυτούς, ότι επιθυμούντες να ευρύνωσι την προδιετίας αναγγελθείσαν υπέρ ανοικοδομήσεως Νηπιαγωγείου δωρεάν αυτών, απεφάσισαν νυν να ανοικοδομήσωσιν Αστική Σχολήν αρρένων δια την πόλιν Λευκωσίας δια δαπάνη 2065 λιρών εν αις συμπεριλαμβάνεται και η εκ λιρών 585, δωρεά του αοιδίμου πατρός των Γεωργίου Ιωαννίδη, συνελθούσα η Επιτροπεία των Σχολείων εις έκτακτον συνεδρίαν.» Η Σχολική Εφορεία, ανακηρύσσει τους δωρητές Μεγάλους Ευεργέτες και το νέο σχολείο ονομάζεται Αστική Αντωνίου και Ευγενίας Θεοδότου. Έκτοτε η Σχολική Εφορεία φροντίζει και συντηρεί με ιδιαίτερη προσοχή τόσο το παλιό κτίριο, όσο και το νεότερο. Φέτος σε συνεργασία με τις τεχνικές υπηρεσίες συνέβαλαν στο κτίσιμο νέων αποχωρητηρίων και τη δημιουργία νέου γηπέδου για μπάσκετ, καθώς και χώρου στάθμευσης.
Η ίδρυση της Αστικής Σχολής υπήρξε για την περιοχή «ύδωρ αλλόμενον εις ζωήν». Σε μια εποχή, όπου η Κύπρος ζούσε κάτω από τον αγγλικό ζυγό, η λειτουργία του σχολείου αυτού θα μπορούσε να χαρακτηριστεί ως αντίσταση και νίκη του φωτός πάνω στο σκοτάδι. Μέχρι το 1925 στη Λευκωσία λειτουργούσαν εντός των τειχών, η Αστική Σχολή Αγίου Σάββα και η Αστική Αγίου Αντωνίου υπό μία διεύθυνση, του Χαράλαμπου Μαραθεύτη, ο οποίος άφησε κληροδότημα στο σχολείο και το διαχειρίζεται η Ιερά Αρχιεπισκοπή.
Το σχολείο οικοδομήθηκε ένα χρόνο αργότερα. το 1926. Το κτίριο του σχολείου είναι πετρόχτιστο δείγμα νεοκλασσικού τύπου, με κίονες και αέτωμα στην πρόσοψη. Αποτελείται από οκτώ μεγάλες αίθουσες διδασκαλίας, γραφείο διευθυντή και δύο άλλες μικρότερες αίθουσες. Οι ευεργέτες εξήγγειλαν νέα δωρεά για επίπλωση και εξοπλισμό του σχολείου. Το σχολείο άρχισε τη λειτουργία του το Σεπτέμβρη του 1926. Πρώτος διευθυντής ο Νικόλαος Αργυρόπουλος και με δασκάλους τους Νέαρχο Τσαρίδη, Γεώργιο Καρκώτη, Χρίστο Χριστοφίδη, Μιχαήλ Μιχαλόπουλο, Νικόλαο Φιλιώτα και Αλέξανδρο Κοσμά.
0 μεγάλος Ευεργέτης του σχολείου, Αντώνης Θεοδότου, τον Αύγουστο του 1928 «μετέστη προς Κύριον», όπως έγραφαν με μεγάλους τίτλους οι εφημερίδες της εποχής εκείνης. Η σύζυγός του Ευγενία εξακολουθεί να έχει το σχολείο υπό την προστασία της, να το επισκέπτεται συχνά και να αναπληρώνει τις ανάγκες του σε εποπτικά και άλλα μέσα. Τον Ιούνιο του 1968 εγκαταλείπει κι αυτή τα εγκόσμια σε βαθιά γηρατειά.
Το σχολείο λειτούργησε από το 1925 μέχρι και το 1940 ως αρρεναγωγείο. Τα κορίτσια της περιοχής φοιτούσαν σε άλλο οίκημα, στο Παρθεναγωγείο Αγίου Αντωνίου που βρισκόταν κοντά στην Αρχιεπισκοπή. Το σχολείο πρωτοπορεί τότε όπως και τώρα σε πολλούς τομείς. Ο Χριστόδουλος Γωγάκης, δάσκαλος του σχολείου το 1931, αναφέρει πως την εποχή εκείνη λειτουργούσε μαθητικό συσσίτιο το οποίο δινόταν σε πολλούς φτωχούς μαθητές. Επίσης, η Ευγενία Θεοδότου δώρισε στο σχολείο ένα Επιδιασκόπιο, το οποίο ήταν πρωτοποριακό και χρήσιμο εποπτικό όργανο κατά τη διδασκαλία πολλών μαθημάτων.
Το 1940 το σχολείο επιτάσσεται από τον αγγλικό στρατό και χρησιμοποιείται για σκοπούς αεράμυνας και αεροπορικής προστασίας. Οι μαθητές του διανέμονται στα γύρω σχολεία. Συγχρόνως κτίζονται και δύο αίθουσες στο χώρο της αυλής του σχολείου, εκ των οποίων η μία λειτούργησε από το 1980 μέχρι το 2003 ως Παιδική Βιβλιοθήκη του Υπουργείου Παιδείας για όλα τα παιδιά της Λευκωσίας.
Το σχολικό έτος 1946-47, το σχολείο επανανοίγει τις πύλες του ως μικτό, με την ονομασία Πρότυπος Αστική Σχολή Αγίου Αντωνίου με διευθυντή τον κ. Αντώνη Νικολαϊδη. Οι πρωτοπορίες συνεχίζονται. Ο Μιχαήλ Τροκούδης, διευθυντής της Σχολής από το 1949- 1952, ανέφερε ότι το έτος 1952, εγκαταστάθηκαν μεγάφωνα στις τρεις ανώτερες τάξεις, μέσω των οποίων τα παιδιά απολάμβαναν μουσικές, κατά τις ώρες του μαθήματος της Μουσικής, της Τέχνης και σε άλλες ώρες που επιτρεπόταν η χρήση τους. Εγκαταστάθηκαν ηλεκτρικά κουδούνια σε όλες τις τάξεις. Η Ευγενία Θεοδότου ενίσχυσε το ταμείο της Σχολής με δωρεά 100 λίρες. Επίσης, άρχισε τη λειτουργία του και Μαθητικό Παντοπωλείο. Μέλη του ήταν 37 παιδιά από όλες τις τάξεις, που κατέθεσαν ένα σελίνι. Κέρδισαν 12 λίρες περίπου, τα οποία σύμφωνα με απόφαση των μελών διαμοιράστηκαν στους μετόχους του.
Η συμβολή των γονέων στην όλη προσπάθεια του σχολείου δεν ήταν μικρή. Ο Σύνδεσμος Γονέων που ιδρύθηκε το 1950 από την εποχή του Μ. Τροκούδη πρόσφερε και εξακολουθεί να προσφέρει πολλά στο έργο του σχολείου, ιδιαίτερα στην ευημερία των παιδιών του σχολείου. Σήμερα, ο Σύνδεσμος Γονέων με δικές του ενέργειες δημιούργησε κήπο με γρασίδι και το εργαστήρι των Ηλεκτρονικών Υπολογιστών, καθώς και συνέβαλε ενεργά, μαζί με τη Σχολική Εφορεία Λευκωσίας, στην αντισεισμική αναβάθμιση και συντήρηση του σχολείου το 2002, καθώς και το γήπεδό μας. Επίσης, με τις διάφορες εκδηλώσεις που πραγματοποιεί κατά τακτά χρονικά διαστήματα ενισχύει οικονομικά το σχολείο και το εκπαιδευτικό έργο που επιτελείται σε αυτό. Ακόμη, με δική του πρωτοβουλία, το 1988 προσλαμβάνει Γραμματέα, η οποία εξυπηρετεί το Σύνδεσμο και το σχολείο μέχρι σήμερα.
Με την ανεξαρτησία της Κύπρου το 1960, ο μαθητικός πληθυσμός αυξάνεται και το σχολείο χωρίζεται σε δύο κύκλους, με δύο διευθυντές. Το Κατώτερο με τις τάξεις Α’ και Β’ και το Ανώτερο με τις τάξεις Γ’, Δ’, Ε’ και Στ’. Για το λόγο αυτό χτίστηκε καινούριο κτίριο στην αυλή του σχολείο, που αποτελείτο από 5 μεγάλες αίθουσες και γραφείο διευθυντή. Ο Σύνδεσμος Γονέων συνεχίζει την δική του προσφορά ιδρύοντας το 1986 Νηπιαγωγείο, που στεγάζεται στο χτίριο αυτό. Το 1990, το Νηπιαγωγείο γίνεται ανεξάρτητο κοινοτικό Νηπιαγωγείο και στεγάζεται μέχρι σήμερα στο νέο κτίριο.
Με την αύξηση των μαθητών στη Λευκωσία, το 1967 ανεγείρεται νέο κτίριο παραπλεύρως του πρότυπου σχολείου με ακόμη τρεις αίθουσες, σκηνή και παρασκήνια με σκοπό να χρησιμοποιούνται και ως αίθουσα πολλαπλής χρήσεως για κάλυψη των αναγκών του σχολείου. Αργότερα το 1980, ανεγείρονται ακόμη τέσσερις αίθουσες διδασκαλίας στον πρώτο όροφο του κτιρίου αυτού.