Born in Stoke Newington in North London, Andy Theodosiou began his career as a trainee with local professional side Tottenham Hotspur. Soon after signing professional terms, he transferred to Norwich City. The Official NCFC club handbook 1990-91 lists Andy as a young professional alongside Robert Ullathorne, Adrian Pennock, Jason Minett , Lee Power , Robert Taylor and current first team regular Daryl Sutch. Andy played 36 reserve team games, out of a total of 38, in the 1989-90 season. Only Adrian Pennock played more reserve games.

Andy did not break into the City first team and transferred to Hereford United in 1991/92 where he made 42 league games. A spell with Brighton preceded a drop into non-league football with Dover of the Vauxhall Conference in June 1995. Andy spent a large part of the 1995/96 season with Crawley of the Dr Martens League. He joined Essex side Billericay Town of the ICIS League First Division in September 1997. He made 29 appearances during 1997/98 scoring five times.

Andy joined Harlow Town and played in their 5-0 thrashing of Diss Town in the FA Cup first qualifying round. However in the autumn of 1999, he moved on to join Ryman League Division Two side Windsor and Eton. Andy joined Ryman League Division Three newcomers Arlesey Town in 2000. In June 2001, he was linked with a return to Harlow but stayed on and was appointed to the position of player-coach.

At the end of December 2004, Andy left Arlesey to join Hemel Hempstead Town.