"All the Times I Cried" is the debut solo single by Texas lead singer, Sharleen Spiteri, from her debut solo album, Melody. It was digitally released in the U.K. on June 30, 2008, and physically released on July 7, 2008. It was taken from The Shangri Las song 'Out In The Streets'.
The music video entails Spiteri having a conversation with a lover over the telephone, potentially breaking up with her. She is heard saying, "I just can't do it anymore". Following this, viewers see two other girls auditioning for a singing role in French Theatre, while Spiteri snoops around looking sad, and then performs - impressing the judges.