Nichols was born in Ogden, Utah, United States. His father was a college music professor, and Nichols was something of a child prodigy, playing difficult set pieces for his father's brass band by the age of 12. Young Nichols heard the early recordings of the Original Dixieland Jazz Band and later those of Bix Beiderbecke, and these had a strong influence on him. His style became polished, clean, and incisive.
In the early 1920s, Nichols moved to the Midwest and joined a band called the Syncopating Seven. When that band broke up, he joined the Johnny Johnson Orchestra and went with it to New York City in 1923. In New York, he met trombonist Miff Mole, and the two were inseparable for the next decade. Before signing with Brunswick, Nichols and Mole recorded for Pathé-Perfect under the name the Red Heads.
Nichols could read music and easily gained studio work. In 1926, he and Mole began recording with a variety of bands as Red Nichols and His Five Pennies. Few of these groups were quintets; the name was a pun on "nickel". With the Five Pennies, he recorded more than 100 sides for Brunswick. He also recorded as the Arkansas Travelers, the California Red Heads, the Louisiana Rhythm Kings, The Charleston Chasers, Red and Miff's Stompers, and Miff Mole and His Little Molers. During some weeks in this period, Nichols and his bands were recording 10 to 12 2-sided records.
Nichols' band started with Mole on trombone and Jimmy Dorsey on alto saxophone and clarinet. Other musicians in his bands in the following decade included Benny Goodman (clarinet), Glenn Miller (trombone), Jack Teagarden (trombone), Pee Wee Russell (clarinet), Joe Venuti (violin), Eddie Lang (banjo and guitar), and Gene Krupa (drums). The Five Pennies' version of "Ida, Sweet as Apple Cider" was a surprise hit record. It sold over a million copies and was awarded a gold disc by the Recording Industry Association of America. His composition "Nervous Charlie Stomp" was recorded by one of the top jazz bands of the 1920s, Fletcher Henderson's orchestra, and released as a 78 single.