It was issued on Mushroom Records in Australia and was Kelly's first solo studio album after disbanding his previous group, The Messengers.

The cover art for Wanted Man is a colophon rendering of Australia's legendary outlaw Ned Kelly (no relation) as a guitarist and was painted by David Band.

[3] In late 1992, when living in Los Angeles, Kelly recorded ten tracks for his next album, Wanted Man, at three studios: Stagg St, Clearlake and O'Henry.

[5]: 424–5  The lead single, "Songs from the Sixteenth Floor" was written by Kelly with John Clifforth of Deckchairs Overboard.

[9] In the first song, the man moves from being newly married to having children and problems with a drug addiction and undergoing rehab to returning to the family home.

[5]: 353–4  "Everybody Wants to Touch Me" describes how a pregnant woman becomes the object of curiosity, wonder or revulsion,[5]: 137–40  although some believe the song relates to a celebrity being the centre of attention (see Paul Kapsis' cover version).

The cover art for Wanted Man is a colophon rendering of Australia's legendary outlaw Ned Kelly (no relation) as a guitarist and was painted by David Band.

[14] Rolling Stone's Paul Corio observed that having Ned Kelly on the cover "makes perfect sense.

Keeping a low profile Down Under, Paul Kelly periodically emerges with albums that raid the storehouse of critical praise, then he retreats to mine poetic gold".

[13] Corio felt the music was "folk, reggae, midtempo rock, jazz-inflected pop and hard-edged ballads – Kelly swings them all deftly".

[13] Allmusic's William Ruhlmann was less favourable and said "[it] was familiar folk-rock, with Kelly singing romantic lyrics over acoustic and electric guitars and a rhythm section.