Wheeler's career in music began at university in a cover band called Melt City, alongside Hal Ritson, now of The Young Punx, Kev Dowd, now of Lowbrow, James Woods, now of Jam Sandwich and Dom Wilhelm, (of 1990s UK pop punk act Satellite Beach).
Virginia featured repeatedly as guests on BBC Radio, particularly Janice Long, Jonathan Ross, Gyles Brandreth, Nicky Campbell and Ned Sherrin, as well as TV appearances in Northern Ireland on the Benny Hill Show.
[citation needed] In 2002, her work with London gospel band Citizen K led to an introduction to Dave Hemingway of the Beautiful South.
By 2003, with the release of "Gaze", Wheeler was a member of the band, appearing live first at a Carling Homecoming at the Welly Club in Hull on 18 September 2003.
She was dubbed Alison 'Lady' Wheeler jokingly by her bandmates in The Beautiful South who felt that her demeanour and education at Trinity College, Cambridge, was in contrast to the band's trademark working-class northern image.