In 1978, Heflin was elected to the United States Senate to succeed fellow Democrat John Sparkman, who had been Adlai E. Stevenson's running mate in the 1952 presidential election. Heflin won his party's nomination by defeating U.S. Representative Walter Flowers of Tuscaloosa, a longtime George C. Wallace ally. The 1966 Republican gubernatorial nominee, former U.S. Representative James D. Martin of Gadsden, announced that he would challenge Heflin. But Martin switched to a second Senate race for a two-year term created by the sudden death of Senator James B. Allen, leaving Heflin without a Republican opponent.