Kelly est né à Adélaïde, en Australie-Méridionale. Il était le sixième sur neuf d'une famille catholique irlandaise. Il commença une année d'étude supérieure à l'université Flinders mais l'arrêta vite et se mit à écrire et composer.
Sa carrière est divisée en quatre périodes: d'abord Paul Kelly & The Dots, ensuite Paul Kelly & the Coloured Girls, puis Paul Kelly & The Messengers et enfin en artiste solo (dans lequel on peut trouver différents projets parallèles).
À la fin des années 1970, Kelly était le chanteur principal du groupe "The High Rise Bombers", lorsque, après sa dissolution, il créa le groupe Paul Kelly & The Dots. Le groupe fonctionna dans la période 1978 à 1982 et sortit deux albums. Cette période fut suivie par deux années d'incertitude et d'abus de drogues. Kelly travailla en tant que parolier mais n'a pas pu trouver de contrat avec une maison de disques. En 1985, il publia seul un album solo (appelé POST), avant de rejoindre le groupe Paul Kelly & The Girls Coloured avec lequel il a sorti deux albums.
À la fin des années 1980, le groupe changea de nom pour devenir Paul Kelly & The Messengers. À partir de 1992, il va se produire seul (même s'il a collaboré avec d'autres artistes et a eu des projets autres pendant cette période). En 1999, il publie la compilation Songs From The South, reprenant des chansons de tous ses différents courants artistiques. En à Melbourne, il a joué 100 de ses chansons dans l'ordre alphabétique, pendant plus de deux nuits. Une émission similaire a été montée à l'opéra de Sydney, en .
Pendant son temps seul, Kelly a également travaillé à composer des musiques pour le cinéma et la télévision tels que Lantana, Silent Partner et One Night The Moon en 2001; Fireflies en 2004 ou Jindabyne, Australie en 2006.
