Gordon was heavily influenced by Ernest Tubb, Bob Wills, and Jimmie Rodgers as a child. He won a radio talent show as a teen and left high school to be the lead singer of his own band, which included fiddle player Jimmy Bryant. His parents demanded that he return to school and give up the band; he did so, though he moonlighted with a band called Pee Wee Mills & the Twilight Cowboys, who operated out of Gulfport, Mississippi. He formed a new Western swing band of his own at age 21 and began touring the Southeast United States. Gordon served in the Army briefly during the Korean War; while there he met Roger Miller, whom he later helped get signed.
In June 1952, an employee of RCA Victor heard Gordon playing in a contest in Atlanta and told executive Steve Sholes about him. Gordon signed with RCA soon after and began recording for the label in the fall. He appeared on the Grand Ole Opry and supported Ernest Tubb, Elvis Presley, and Hank Snow on tour. His records sold modestly, though they never charted; he remained on RCA for two years, and when his contract expired he was snapped up by Mercury Records. Gordon's style changed while on Mercury, for a number of possible reasons. The label let him record much of his own material, he worked extensively with producer Pappy Daily, and the nascent rock & roll movement had changed tastes. His recordings of 1956-57 are a mix of Western swing, rock and roll, and straight country music.
He played regularly in Mobile, Alabama and toured the South sporadically. He recorded with Dollie Records at the end of the 1950s, his last major contract; he continued performing locally for some time after that. He ran a dance club in Georgia in the 1970s, and returned to rockabilly performing in the 1980s as the Europeans revived it.