Stempniak lived near an ice hockey rink as a child, and knew the owner who let him practice whenever he could. Stempniak graduated from St. Francis High School in Athol Springs, New York in 2001, and wanted to continue to play hockey, but enrolled in college after insistence from his parents. Stempniak enrolled at Dartmouth College, where he majored in economics. He became a top player for the ice hockey team at Dartmouth, as he was named a two-time All American and team captain.
Stempniak was drafted by the St. Louis Blues in the fifth round, 148th overall by the St. Louis Blues in the 2003 NHL Entry Draft. In the 2006-07 season, his first full season with the Blues, Stempniak led the team in goals with 27, while he was just 23 years of age. He and David Backes joined Jay McClement to form one of the NHL's youngest lines. In the 2007-08 season, Stempniak's production dropped, as he only managed 38 points in 80 games. His shooting percentage was less than half of what it was the year prior, despite having taken a roughly equal number of shots.
On November 24, 2008, Stempniak was traded by the Blues to the Maple Leafs for Alex Steen and Carlo Colaiacovo. Stempniak wears number 12 with the Maple Leafs, just as he did with the Blues.