Herring was first elected to the City Council in February 1974 in a special election to fill the unexpired term of Liston Corcoran, who died in office. He retained the seat by winning a four-year term in the 1975 election and was re-elected in 1979 and 1983. After that election he served for the next two years as Council President, turning over the gavel to William Bell in 1985.
Herring was re-elected to a fourth four-year term in 1987, but had to enter the ring again when the council was divided into district representation in 1989. He won the District 3 seat in the 1989 Birmingham municipal election. Jimmy Blake took over that seat in the 1993 Birmingham municipal election.