Apostolakis inledde sin karriär med Panetolikos men flyttade senare till Olympiakos. Med klubben vann han Alfa Ethniki 1986/1987. Apostolakis blev så småningom lagkapten.
Efter fem säsonger med Olympiakos gjorde Apostolakis 1990 den "förbjudna" flytten till ärkerivalerna Panathinaikos. Detta ledde till att det årets upplaga av den grekiska supercupen fick skjutas upp på grund av oro för kravaller mellan lagens supportrar.[1][2][3] Apostolakis kom att spela med Panathinaikos till 1999 och vann under de åren tre ligatitlar, fyra cuptitlar och en supercuptitel.[4]