"The Queen of Starting Over" is the third single released from British singer-songwriter Beverley Knight's fifth studio album, Music City Soul. "The Queen of Starting Over" was a download only release, Knight's first single in her career that was not be released on a CD single format. The single was the second of a two-part digital single to be released containing tracks from her live performances at the iTunes live festival from July, 2007 (the first part was a live EP release of "No Man's Land") . The release date for the single was 15 October 2007, a week prior to her UK tour supporing the Music City Soul album.