The original barbecue restaurant was opened in a small building at 6633 Old Springville Road by Randy Walls in the 2003. In the summer of 2010, a second restaurant was opened at 163 Main Street and the menu was expanded to include the meat and three fare.
- W., Bunny (February 9, 2012) "Legends Smokehouse Restaurant." Birmingham Weekly
- McGough, Crystal (July 12, 2012) "Both Legends Smokehouse locations close." Trussville Tribune