King made his professional debut on September 20, 2003, defeating Matthew Fendley via first-round technical knockout (TKO) in Kalamazoo, Michigan.
He then had two wins (both by KO) and two losses (both by points decision) before defeating Joe Johnson at the International Convention Center in Sarasota.
After the bout with Briggs, King suffered a number of defeats, at the hands of boxers including Jason Estrada, Chazz Witherspoon, Derric Rossy, and Kevin Johnson, losing via points decision each time.
Following his loss to Kevin Johnson, King had a winning streak of five, all by knockout, defeating, among others, future WBC heavyweight champion Bermane Stiverne in 2007.
He defeated the then undefeated Australian prospect Bowie Tupou via KO in the second round in their bout at Agua Caliente Casino in Rancho Mirage.