Kelly attended Rostrevor College, a Christian Brothers school, where he played trumpet and studied piano, became the first XI cricket captain, played in the first XVIII football (Australian rules), and was named dux of his senior year. He studied arts at Flinders University in 1973, but left after a term, disillusioned with academic life. He began writing prose and started a magazine with some friends. Kelly spent several years working odd jobs, travelling around the country and learning guitar before he moved to Melbourne in 1976.