Robinson learned to play clarinet as a teenager and moved to New York in 1923 after playing locally in Virginia. In New York he quickly found work both performing and recording, with the Blue Rhythm Orchestra, June Clark, Duke Ellington, Billy Fowler, the Gulf Coast Seven, Fletcher Henderson, Lionel Howard, Clara Smith, and Elmer Snowden. He played in Leon Abbey's group on a tour of South America in 1927, and the following year became a member of McKinney's Cotton Pickers.
In the 1930s Robinson worked with Lil Armstrong, Willie Bryant, Blanche Calloway, Roy Eldridge, and with Teddy Wilson accompanying Billie Holiday. His career continued robustly in the 1940s, including work with Louis Armstrong, Lucky Millinder, and Benny Morton; in 1945 he joined Claude Hopkins's band, where he would remain until 1952. Later in the 1950s he worked with Fletcher Henderson again and with Red Allen and Freddie Washington, in addition to leading his own ensemble in 1953.