It was in Japan that Nelson attended a concert by the Tokyo Philharmonic Orchestra and heard Maurice Ravel's Ma mère l'Oye and Paul Hindemith's Symphony in E Flat.

After completing his degree Nelson moved to New York City, playing with Erskine Hawkins and Wild Bill Davis, and working as the house arranger for the Apollo Theater in Harlem.

[4] Nelson worked as an arranger on large ensemble albums for Thelonious Monk, Cannonball Adderley, Sonny Rollins, Eddie "Lockjaw" Davis, Johnny Hodges, Wes Montgomery, Buddy Rich, Jimmy Smith, Billy Taylor, Stanley Turrentine, Irene Reid, and Gene Ammons.

Films scored by Nelson include Death of a Gunfighter (1969), Skullduggery (1970), Dial Hot Line (1970), Zig Zag (1970) and The Alpha Caper (1973).

During this productive time he also arranged and produced albums for pop stars such as Nancy Wilson, James Brown, The Temptations, and Diana Ross.

Along with his big-band appearances (in Berlin, Montreux, New York, and Los Angeles), he led a small group that included John Klemmer, Ernie Watts, Freddie Hill, and Frank Strozier in a United States Department of State-sponsored tour of West Africa in 1969.

Less well-known is the fact that Nelson composed several symphonic works[citation needed], and was also deeply involved in jazz education, returning to his alma mater, Washington University, in the summer of 1969 to lead a five-week-long clinic that also featured such guest performers as Phil Woods, Mel Lewis, Thad Jones, Sir Roland Hanna, and Ron Carter.

Among the student participants at the Washington University Summer Jazz Institute were saxophonists Julius Hemphill, Oliver Lake, and Hamiet Bluiett, who later co-founded the World Saxophone Quartet with David Murray.