Salmon formed the first lineup of the Surrealists in mid-1987, with Brian Henry Hooper on bass and Tony Pola on drums. He formed the band to record the album Hit Me with the Surreal Feel, using minimalist lo-fi approaches to recording a basic trio: recording the band live with microphones around the studio capturing the entire sound rather than one instrument per track. The recording and mixing cost was A$240 total. The band also played live around Perth in mid-1987. The album was released in October 1988.

The Surrealists did a few songs by the Scientists (particularly "Shine" from The Human Jukebox) and had a similar sound in that Salmon remained the leader and primary songwriter, but the feel of the music was notably different, far less tense and confrontational.

The second album Just Because You Can't See It ... Doesn't Mean It Isn't There was recorded more conventionally in 1989 and released in early 1990. Comparing this album with The Human Jukebox, there is a similarity in songwriting but a difference in feel is readily apparent. The band's third album Essence was released in 1991, followed by Sin Factory in 1993, which arguably gained the most attention for the band. The sound by now was strong rock riffery, also blending their take on Blaxploitation music.

When The Beasts of Bourbon reformed in early 1988, Salmon started touring with that band too. When James Baker and Boris Sujdovic left The Beasts of Bourbon to go full-time with The Dubrovniks, Hooper and Pola joined to replace them.

Salmon fired Tony Pola from the Surrealists in 1993, replacing him with Greg Bainbridge. Brian Hooper later left after the "Kim Salmon and the Surrealists" album and was replaced by Stu Thomas in 1995. This new trio put out Ya Gotta Let Me Do My Thing in 1997, touring Australia, Europe, and the U.S. A horn section was added to the band that included trumpet player Leon de Bruin and saxophonist Michael Redman.

In 1999, Salmon renamed the band Kim Salmon and the Business, and released one album "Record" in 1999. Stu Thomas remained on bass and Phil Collings was recruited on drums in 2000.

In September 2006, Kim Salmon and the Surrealists 'reformed' for a show in Spain at Azkena Rock Festival. This line-up of Kim Salmon (guitar/vocal), Stu Thomas (bass) and Phil Collings (drums) also played later in Australia.

2010 marked the release of the album Grand Unifying Theory, the first Kim Salmon and The Surrealists record for 13 years. Line-up featured Kim Salmon (guitar/vocal/sampler), Stu Thomas (bass) and Phil Collings (drums). The band was recorded live during rehearsals. The results were sifted through by Salmon and co-producer Mike Stranges, spliced together in some cases (ala Miles Davis' "Bitches Brew"), and made into songs.

In June 2020, during COVID lockdowns the band performed 2 improvised livestream gigs from Rolling Stock Studios, Melbourne. These were seen by 7500 worldwide. The livestreams were also recorded then released as the double-LP "Rantings From The Book Of Swamp".

In 2022 the band completed the "Ya Gotta Let Me Swamp My Rantings" tour of Australia, included the current lineup, plus previous drummer Greg Bainbridge. Two sets featured the 2 different lineups, first performing the current "Rantings" LP, followed by 1997's "Ya Gotta Let Me Do My Thing" album.

• Hit Me with the Surreal Feel (1988), Black Eye Records
• Just Because You Can't See It ... Doesn't Mean It Isn't There (1989), Black Eye Records
• Essence (1991), Red Eye/Polydor
• Sin Factory (1993), Red Eye Records/Polydor Records
• Kim Salmon and the Surrealists (1995), Red Eye/Polydor Records
• Ya Gotta Let Me Do My Thing (1997), Half a Cow Records/Citadel Records
• Grand Unifying Theory (2010), LTI/Bang! Records
• Ya Gotta Let Me Do My Thing (2015), vinyl re-issue, Bang! Records
• Rantings From The Book of Swamp (2020)

• Kim Salmon and the Surrealists (Encyclopedia of Australian Rock and Pop by Ian McFarlane)
• Story behind The Surreal Feel album and fish cover art