She has come to be recognised as a symbol of the Rainbow Nation, Desmond Tutu's vision of a multicultural South Africa in the post-apartheid era.

Among her musical influences she lists Ella Fitzgerald and Debbie Harry, as well as Louis Armstrong and the crooners of the mid-20th century.

At the age of ten, she debuted as an actor, dancer, and singer in a Johannesburg production of the musical Annie.

[5] At age 17,[6] during her final year at Greenside High School, she joined the crossover band Mango Groove.

While work on Starehe was still progressing, Johnston recorded a second solo album, Africa Blue (EMI, 2004).

[11] 2006 saw not only the release of Starehe, but EMI's reissue of Fearless and Africa Blue as a double album called The One and Only.