Battaglia began playing hockey in Park Ridge, Illinois. He played on the three-time NCAA National Championship Lake Superior State University Lakers from 1994–1997. Battaglia was then drafted in the sixth round, 132nd overall, by the Mighty Ducks of Anaheim in the 1994 NHL Entry Draft.
On March 18, 1997, Battaglia was traded by the Mighty Ducks to the Hartford Whalers for Mark Janssens. He made his professional debut in the 1997-98 season with the New Haven Beast of the AHL before making his NHL debut with the Carolina Hurricanes in their inaugural season. Battaglia established himself as a NHL regular with the Hurricanes, enjoying his most successful period as a third of the prominent "BBC" line (Rod Brind'Amour, Battaglia, and Erik Cole) during the Hurricanes' 2001–2002 Stanley Cup run.
During the 2004 NHL lockout, Bates Battaglia joined his younger brother Anthony on the Mississippi Sea Wolves of the ECHL for the 2004–05 season on February 21 2005.
On October 2, 2005, Battaglia was signed by the Toronto Marlies of the AHL to a one-year deal. The following season, Battaglia signed as a free agent to the Marlies' parent club, the Toronto Maple Leafs, to a one-year contract on July 2, 2006. Battaglia re-signed as a free agent with the Maple Leafs to a two-year contract on July 2, 2007.
On December 13, 2007, Battaglia was assigned to the Toronto Marlies on a conditioning assignment, however he was left in the minors for the duration of the season. Battaglia was again assigned to the Marlies at the start of the 2008-09 season.