His first published song, "It's the Falling Apart that Makes You", was written after listening to Van Morrison's "Astral Weeks" at the age of 19, although in an interview with "Drum Media" he recalled writing his first unpublished song: "It was an open-tuning and had four lines about catching trains. I have got a recording of it somewhere. It was called 'Catching a Train'. I wrote a lot of songs about trains early on, trains and fires, and then I moved on to water". In 1976, Kelly appeared on "Debutantes", a compilation album featuring various Melbourne-based artists, and joined pub-rockers The High Rise Bombers from 1977 to 1978. The High Rise Bombers included Kelly (vocals, guitar, songwriter), Martin Armiger (guitar, vocals, songwriter), Lee Cass (bass guitar), Chris Dyson (guitar), Sally Ford (saxophone, songwriter), John Lloyd (drums), and Keith Shadwick (saxophone). Chris Langman (guitar, vocals) replaced Dyson in early 1978. never played with the High Rise Bombers and is incorrectly listed as a guitarist on the "Melbourne Club" album. In August, after Armiger left for The Sports and Ford for The Kevins, Kelly formed Paul Kelly and the Dots with Langman and Lloyd. The High Rise Bombers recorded two tracks, "She's Got It" and "Domestic Criminal", which appeared on "The Melbourne Club", a 1981 compilation by various artists on Missing Link Records.