Born in Lake Charles, Louisiana, and raised in Los Angeles, Nelson got his early musical training in church. In 1957, he and several friends formed the Hollywood Flames, a prolific doo-wop group, and soon had a major hit 'Buzz, Buzz, Buzz' in 1958, on which Nelson sang lead.

In 1960, Nelson and another Flame, Bobby Byrd (who also recorded solo as Bobby Day), began recording together as Bob & Earl. However, these early releases had little success and Byrd restarted his solo career.

In 1962, Nelson recruited a second 'Bob', Bobby Relf (who also used the stage names of Bobby Garrett and Bobby Valentino). This duo recorded several singles for different labels before recording 'Harlem Shuffle' in 1963. When released on the Marc label, it became a modest hit on the R&B chart, but its major success came as late as 1969 when it was re-released in the UK and was a Top 10 hit.

By that time, Nelson had achieved further success as a solo artist under the name Jackie Lee.

Bob & Earl toured together after the 1969 reissue but split up for the last time in the early 1970s.