The song was released in May 1983 as the second single from her fourth studio album, Foreign Affairs (1983).

Late in 1981, O'Neill moved from New Zealand to Sydney, New South Wales, Australia to pursue her music career.

[1] It was here that she wrote "Maxine", a song that chronicled the life of a Kings Cross prostitute.

[2] In a 2016 interview, O'Neill said; "I was living in a hotel in Kings Cross when I got the inspiration to write "Maxine".

She was always out there working at 3am when we'd get home bleary-eyed from a gig"[1] Two music videos were filmed: one in New Zealand[3] for general audiences,[4] and the other in Sydney with far more explicit themes.