Kostakis Costa startte zijn carrière bij APOEL Nicosia, waar hij in totaal 9 seizoenen zou spelen. Daarna speelde hij een seizoen bij FC Utrecht, om vervolgens weer terug te keren naar Cyprus om te gaan spelen bij Apollon Limassol. Hierna kwam hij nog even uit voor Olympiakos Nicosia