The song became a crossover hit and a dance craze, in many ways foreshadowing the popular success of rock and roll a few years later.

It was successfully recorded by many other musicians including Lucky Millinder, Roy Milton, Tommy Dorsey, Frank Sinatra, Lionel Hampton, Louis Armstrong, Chubby Checker, Bo Diddley, Otis Redding, Quincy Jones, Canned Heat, Coast to Coast, Brendan Bowyer and Crystal Swing.

The tune, structured around a twelve-bar blues progression, was originally recorded by Paul Williams and his band, credited as His Hucklebuckers, in New York City, on December 15, 1948, with producer Teddy Reig.

The tune itself was strongly influenced by "Now's the Time", a composition by Charlie Parker who first recorded it in 1945, also produced by Reig for the Savoy label, with a band that included Dizzy Gillespie, Miles Davis, and Max Roach.

[3][4][5] Millinder later took court action against Gibson and United Music, the publishing company, for copyright infringement, but eventually dropped the case while retaining the rights to "D'Natural Blues".

[10] The success of Williams' instrumental recording led to words being written to the tune, by Tin Pan Alley lyricist Roy Alfred.