After growing up in Adelaide, Kelly travelled around Australia before settling in Melbourne in 1976. He became involved in the pub rock scene and drug culture, and recorded two albums with Paul Kelly and the Dots. Kelly moved to Sydney by 1985, where he formed Paul Kelly and the Coloured Girls. The band was renamed Paul Kelly and the Messengers, initially only for international releases, to avoid possible racial interpretations of the word "coloured". At the end of the 1980s, Kelly returned to Melbourne, and in 1991 he disbanded the Messengers. Kelly was married and divorced twice; he has three children and resides in St Kilda, a suburb of Melbourne. Dan Kelly, his nephew, is a singer and guitarist in his own right. Dan performed with Kelly on "Ways and Means" and "Stolen Apples". Both were members of Stardust Five, which released a self-titled album in 2006. On 22 September 2010 Kelly released his memoir, "How to Make Gravy", which he described as "it's not traditional; it's writing around the A–Z theme – I tell stories around the song lyrics in alphabetical order". His biographical film, "", directed by Ian Darling, was released to cinemas in October 2012.