Gordon first led a band called the Pretzel Five when he was still in high school. He moved to Chicago in the mid-1920s, where he played with the Seattle Harmony Kings and Elmo Mack's Purple Derby Orchestra. He led a band which played the 1933 World's Fair in Chicago. In 1936 he relocated to New York City, where he founded his first professional band, taking the stage name Gray Gordon during a touring engagement at the Hotel Chase in St. Louis.
Gordon called his band the Tic Toc Rhythm, based on the distinct clock-like rhythmic figure played on temple blocks by his percussionist Frank Adams. This was often accompanied by a trombone figuration prior to the beginning of songs, which helped identify the band to listeners during radio performances. For several years from 1939, he held a six-month engagement at the Hotel Edison in New York, whose performances were broadcast nightly on radio, and toured the other half of the year. His group started as a smaller ensemble – three brass instruments, three saxophones, and three rhythm instruments – but in 1940 he expanded it to twelve musicians or more, plus vocalists. He recorded several times for Bluebird and Victor during the period 1940–41; he also recorded four sound films in 1941 playing swing jazz. One of his signature songs, "I Am an American", was a popular tune at war bond rallies during World War II. He married dancer Noel Carter in 1941; they divorced in 1949.
Gordon dissolved his band in 1945 and later worked in artist and repertory in the music business, including for Les Paul, Mary Ford, and King Guion. He also worked in public relations for hotels in Miami. He was living in New York City in 1976 when he died of cancer at St. Luke's Hospital. He is buried at Oakland Cemetery in his home town of Freeport.