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 (19 points) 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. On February 25, 2018, Letestu was traded to the Nashville Predators in exchange for Pontus Åberg.