Born on October 3, 1970, in Nea Karvali, Kavala prefecture, Kostenoglou started his football career with local club A.O. Karvali. He was acquired by SKODA Xanthi in 1991 and came to AEK in 1994. He was a mainstay of AEK's defence until 2005 when he decided to retire.
After retirement, Kostenoglou worked in the youth academy of AEK until Lorenzo Serra Ferrer was sacked as AEK's head coach. Kostenoglou was then picked to succeed Ferrer in that post.
In November 2008, he was named head coach of Asteras Tripolis. He was picked in 2011 to coach AE Larisa but could not save them from relegation. In October of the same year he returned to AEK replacing Manuel Jimenez.