Iraklis was one of the first clubs which encouraged volleyball as one of the main activities before the World War II. After the war, it was always among the top teams in Greece. The first Greek National Championship was played in 1968 and Iraklis, apart of its own success, was able to contribute to the National Teams with plenty of players. During the 1970s, Iraklis participated twice in the championship finals, thanks to the contribution of Nikos Antoniadis, the greatest athlete in the history of volleyball in Greece. Many Championships were lost because of the Athens clubs-favored system of play. In 1987, 1989 and 1992 Iraklis made it to European Cups and in 1997 came the outburst of the team.
Thanks to an organized effort, Iraklis played three consecutive Championship finals and finally won its first title -the Greek Cup- in 2000. Two years later, it won both the Championship and Cup titles, while finishing third in the CEV Champions League Final Four held in Opole, Poland. The next four years Iraklis dominated in Greek Volleyball, confirming his superiority by winning one Championship (2005), three Greek Cups (2004, 2005, 2006) and two Greek Super Cups (2004, 2005), but mostly by participating in three more CEV Champions League Final Fours. In 2004 in Belgorod, Russia the team finished in the fourth place. Next year, the presence of world-class players such as Lloy Ball, Thomas Hoff and Clayton Stanley helped the team to reach the Final Four which took place in Thessaloniki, Greece. Iraklis beat Lokomotiv Belgorod in the semi-final, but lost 1-3 to Tours VB in the final, despite the outstanding support by its fans. In 2006, Iraklis made it again to the final in Rome, Italy to be beaten by Sisley Treviso 3-1. About 4,000 Iraklis fans traveled to Rome to support the team, creating fantastic atmosphere and setting a record for an away crowd in a volleyball game.
The following season marked the beginning of a transitional period. Many of the top players were released from the team, while the budget was cut in half. Even so, the team's dominance in Greece continued. In 2007, Iraklis finished third in regular season, but managed to win the Championship beating Olympiacos S.C. in the semi-finals and Panathinaikos VC in the finals, having both times a disadvantage. The next Championship had the same conclusion. Iraklis defeated Panathinaikos VC in the finals (without losing a single game) and were crowned Champions for the fourth time in their history.