Sykes married Maxine at the beginning of World War II and served in the Army. After the war, Sykes took a job delivering bread for a bakery. When the bakery closed in 1956, the Sykeses opened their first restaurant, The Ice Spot, in Central Park in 1957. By 1965 Sykes was the manager of the Frostop restaurant and root beer stand at 2916 3rd Avenue West (Bessemer Road).
The couple opened Bob's Hickory Bar-B-Q a few years later just down the street. Eventually they tired of the long hours and began franchising the name to more than a dozen operators in North Alabama and Tennessee. In 1966 the couple returned to the barbecue business and opened a new restaurant in Five Points West, then moved two years later to Bessemer.
After Sykes suffered a stroke in 1970, Maxine took over the business, terminating the franchise agreements to focus her attention on the main store, which she managed along with their son, Van. Together the two moved the restaurant to its present location on Bessemer Road in 1977.
- Evans, Amy (September 30, 2006) Interview with Maxine and Van Sykes. Southern Foodways Alliance
- "Maxine Sykes" obituary (January 19, 2015) The Birmingham News
- "Maxine Sykes, co-founder of Bob Sykes Bar-B-Q, dies." (January 19, 2015) Alabamas13.com
- Garrison, Greg (January 23, 2015) "Bob Sykes Bar-B-Q was always 'And Maxine Too': Mrs. Sykes ran legendary restaurant for decades" The Birmingham News