After playing at Western Michigan, Letestu was signed as an undrafted free agent by the NHL's Pittsburgh Penguins on March 22, 2007. He appeared in three regular and two playoff games with the Wilkes-Barre/Scranton Penguins, Pittsburgh's American Hockey League affiliate, when he joined the team at the end of the 2006–07 season. In 2007–08 he appeared in 52 games with Wilkes-Barre/Scranton and six games with the Wheeling Nailers of the ECHL. He then spent the entire 2008–09 season in the AHL. In March 2009, Letestu signed a new two-year contract with the Penguins. Letestu made his NHL debut on November 14, 2009, against the Boston Bruins. He made another appearance with the Penguins before being reassigned to Wilkes-Barre/Scranton. Letestu was called-up again on December 5 and played that night against the Chicago Blackhawks. He received 13:52 of ice time and won a faceoff against John Madden that set up the game's tying goal by Jordan Staal with 31 seconds remaining in the game. Letestu scored his first career NHL goal on February 1, 2010, against Ryan Miller of the Buffalo Sabres, scoring 47 seconds into the first period; the goal was assisted by Tyler Kennedy and Kris Letang. Letestu was one of seven Wilkes-Barre/Scranton players recalled by Pittsburgh after the AHL Penguins were eliminated in the first round of the 2010 Calder Cup playoffs. He appeared in his first Stanley Cup playoff game in the Penguins' second round series against the Montreal Canadiens on May 4 when he replaced the injured Staal as the third-line centre between Tyler Kennedy and Matt Cooke. In Game 5 on May 8, Letestu recorded his first Stanley Cup playoff point with an assist on a second period goal by Sergei Gonchar. Letestu began the 2010–11 season with the Penguins after delivering a strong training camp and pre-season. He finished the pre-season with one goal and five assists in five games. After scoring against the Chicago Blackhawks during pre-season, Letestu said, "I worked hard this summer... the praise is nice but it's only as good as your last game. I just need to keep playing the way I have been and hopefully force somebody to keep me here." He began the 2010–11 NHL regular season equally as strong, scoring game-winning goals in two of his first three games, being named one of the Stars of the Game against Montreal and the New Jersey Devils. Letestu was then named the first star against the Ottawa Senators on October 18, 2010, after scoring a power-play goal and assisting on Evgeni Malkin's goal by winning a faceoff in the Ottawa zone. The performance gave him seven points in his first seven games. Of Letestu, Penguins captain Sidney Crosby said, "He has really made an impact for us." However, Letestu's production dipped into November, as he went 22 consecutive games without scoring a goal. On December 8, 2010, Letestu broke his scoring drought with the first multi-goal game of his NHL career, scoring twice against the Toronto Maple Leafs. On January 18, 2011, Letestu signed a new two-year contract with the Penguins worth an average annual value of $625,000. At the time, he was tenth among all NHL rookies in scoring and had scored three game-winning goals.
On November 8, 2011, Letestu was traded to the Columbus Blue Jackets in exchange for a fourth-round draft pick. Letestu finished the season with 25 points in 62 games split between both clubs. During the 2013–14 and 2014–15 seasons, Letestu was an assistant captain for the Blue Jackets.
After three-and-a-half seasons with the Blue Jackets, Letestu left the club as a free agent on July 1, 2015, after signing a three-year contract with the Edmonton Oilers. During the 2016–17 season, Letestu scored a career-high 16 goals to go along with a career-high 35 points.
Return to Columbus
On February 25, 2018, Letestu was traded to the Nashville Predators in exchange for Pontus Åberg. Later that day, Letestu was traded from Nashville to the Blue Jackets in exchange for a fourth-round pick in the 2018 NHL Entry Draft. Letestu and the Blue Jackets reached the 2018 playoffs but were eliminated in the first round by the Washington Capitals. Letestu went scoreless in six games. On August 14, 2018, Letestu agreed to attend the Florida Panthers' training camp on a professional try-out contract. He was released from his PTO contract on September 24. On September 27, Letestu returned to the Blue Jackets after signing a one-year, two-way contract. He was immediately placed on waivers for the purpose of assignment to the team's AHL affiliate, the Cleveland Monsters.
Winnipeg Jets
Having left the Blue Jackets as a free agent, on July 2, 2019, Letestu signed a one-year, two-way contract with the Winnipeg Jets.
