Το τμήμα πετοσφαίρισης του Α.Ο. Ορεστιάδος αγωνίστηκε για πρώτη φορά το 1971. Το 1984 με τον Ηλία Ιεροκλή στο τιμόνι της ομάδας εξασφάλισε τη συμμετοχή της για πρώτη φορά στην Α΄ Εθνική Κατηγορία. Από το 1989 και μετά αποτέλεσε μία από τις ισχυρότερες ομάδες όχι μόνο του Πρωταθλήματος Ελλάδας αλλά και των ευρωπαϊκών διοργανώσεων.
Τρεις φορές κατέκτησε τη 2η θέση στο Πρωτάθλημα Ελλάδας και άλλες 4 φορές συμμετείχε στην τελική φάση ευρωπαϊκών διοργανώσεων με κορυφαία στιγμή τη 2η θέση στο Κύπελλο Ευρωπαϊκής Συνομοσπονδίας την αγωνιστική περίοδο 1994–1995 όπου απέκλεισε τη μεγάλη τότε Volley Gonzaga Milano του Σίλβιο Μπερλουσκόνι με 3–2 set και αγωνίστηκε στον τελικό με την Pallavolo Parma από την οποία έχασε με 3–0 set.[4][5]