Stoltidis started out at Pontioi Kozani in the fourth division before signing for Iraklis FC, where he spent eleven years. He made his Alpha Ethniki debut for the Thessaloniki-based club in December 1992 but did not become a regular until the 1996 season. In June, 2003, after 234 league matches, he left for Olympiakos, signing a two-year contract.
Stoltidis scored two goals and assisted on another in Olympiakos' 3-0 win vs. Werder Bremen on December 11, 2007 to send his team past the group stage of the Champions' League for the first time in nine years.
Internationally, Stoltidis was a member of the Greece side that reached the 1998 UEFA European Under-21 Championship final. In November 1999, he made his debut for the senior national team and went on to represent Greece at the Athens Olympics in 2004. He has been capped so far (end of 2007) 6 times.
One day before his 33 birthday, Ieroklis Stoltidis was handed an early birthday gift as he received his first Greece call-up under Otto Rehhagel following a long international exile, to play an unofficial friendly against the Czech Republic and Finland in Cyprus on February 5-6. While Ieroklis Stoltidis acknowledged the honor of being invited, he declined the invitation citing that his age will not allow for him to contribute to the level he would like.