Leonidas was born in Westminster, London, the daughter of a Greek Cypriot father and an English mother.

Leonidas started acting in community theatre when she was eight; at nine she acquired an agent and began to work in television.

[2] Notable credits include the television drama Daddy's Girl, the soap opera Night and Day and a 2004 episode of Doc Martin (entitled 'Of All the Harbours in All the Towns') in which she plays Melanie, a local Portwenn 15-year-old girl who develops an unhealthy interest in the surgeon.

In 2005 she starred in Neil Gaiman and Dave McKean's MirrorMask in the dual roles of Helena and the Dark Princess.

She starred as Chloe Koen in the first season of the Crackle crime series Snatch and appeared in the 2018 film Tomorrow.