Fuller learned mellophone as a child before settling on trumpet. He played in a traveling medicine show from age 14, then played with Sammy Stewart in the late 1920s. In 1930 he moved to Chicago and played with Irene Eadie and Her Vogue Vagabonds. He began a longtime partnership with Earl Hines in 1931, remaining with him until 1937, when he took a job with Horace Henderson's ensemble. This gig lasted only a few months, though and after a year with Henderson he returned to duty under Hines again. He left Hines again in 1940 to form his own band, playing at the Grand Terrace in Chicago and the Radio Room in Los Angeles. Among his sidemen were Rozelle Claxton, Quinn Wilson, Omer Simeon, and Gene Ammons. He led bands on the West Coast for over a decade, and played as a side trumpeter and vocalist for many years afterward.
Fuller won the nickname "Rosetta" based on his singing on the 1934 Hines recording of the song "Rosetta".