Ο σύλλογος ιδρύθηκε το 1975, έπειτα από πρωτοβουλία των ανθρώπων του διαλυμένου [[«Γ.Σ. Αλεξανδρούπολης]]», η οποία οδήγησε στη μετονομασία του αθλητικού σωματείου «Κύκλωψ» Μάκρης σε Αθλητικός Όμιλος «η Αλεξανδρούπολις».<ref name="uth">{{cite web |url=http://ir.lib.uth.gr/bitstream/handle/11615/1664/P0001664.pdf?sequence=1&isAllowed=y |title=Η σύγχρονη αθλητική ιστορία της Αλεξανδρούπολης |last=Γιαννακόπουλος |first=Ανέστης |author= |year=2008 |work= |publisher=[[Πανεπιστήμιο Θεσσαλίας]] |location=Κομοτηνή |page= |pages=69, 70, 71 |at= |language= |type= |format=PDF |isbn= |id= |archiveurl=https://web.archive.org/web/20171126173131/http://ir.lib.uth.gr/bitstream/handle/11615/1664/P0001664.pdf?sequence=1&isAllowed=y |archivedate=26 Νοεμβρίου 2017 |deadurl= |accessdate=26 Νοεμβρίου 2017 }}</ref> Η ομάδα μετείχε αρχικά στα πρωταθλήματα της [[ΕΠΣ Έβρου]]. Η περίοδος [[Γ΄ Εθνική ποδοσφαίρου ανδρών 1978-1979|1978–79]] ήταν η πρώτη για την ομάδα στο Εθνικό Ερασιτεχνικό Πρωτάθλημα, όπου τερμάτησε στη 12η θέση του 4ου Ομίλου και υποβιβάστηκε στις τοπικές κατηγορίες.
Την περίοδο [[Γ΄ Εθνική ποδοσφαίρου ανδρών 1980-1981|1980–81]] μετείχε και πάλι στο Εθνικό Ερασιτεχνικό Πρωτάθλημα. Ήταν η περίοδος [[Γ΄ Εθνική ποδοσφαίρου ανδρών 1981-1982|1981–82]] όταν η ομάδα αναδείχθηκε πρωταθλήτρια στον 8ο Όμιλο του Εθνικού Ερασιτεχνικού Πρωταθλήματος, πετυχαίνοντας έτσι την άνοδο στη Β΄ Εθνική κατηγορία. Την περίοδο [[Β΄ Εθνική ποδοσφαίρου ανδρών 1982-83|1982–83]], ο Άλεξ μετείχε για πρώτη φορά στο πρωτάθλημα της Β΄ Εθνικής, όπου τερμάτησε στη 18η θέση του Βόρειου Ομίλου με αποτέλεσμα τον υποβιβασμό τη Γ΄ Εθνική κατηγορία.
