The song was the first and in most parts of the world the only single release from Grace Jones' third album Muse (1979). In most territories it was credited as a double A-side with "Don't Mess with the Messer". The 7" single featured edited versions of both tracks while the 12" included a very slightly different mix of "On Your Knees" and an extended remix of "Don't Mess with the Messer". None of these mixes and edits have been re-issued on CD, just like the Muse album itself, originally released in the year of the so-called anti-disco backlash. The single was ignored by the record-buying public and left little impact on dance music charts in the USA.
The record cover artwork, designed by Richard Bevistein, was featured in Michael Ochs' 1996 book 1000 Record Covers.