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. He played seven years at Olympiakos before making his last transfer to Kerkyra in 2010. This was his last year as a professional as he retired in 2011.
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 scored against Mexico.
He has been capped 6 times for the senior national team. All of his games were friendlies and he did not lose one of them.
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.