Grebeshkov was a first round selection, 18th overall, by the Los Angeles Kings in the 2002 NHL Entry Draft. He was traded to the New York Islanders on March 8, 2006, along with Jeff Tambellini, in exchange for Mark Parrish and Brent Sopel. Having been unable to come to a contract agreement with the Islanders, Grebeshkov returned to Russia to play with Lokomotiv Yaroslavl for the 2006–07 season. On February 18, 2007, Grebeshkov's rights were traded to the Edmonton Oilers in exchange for defenceman Marc-André Bergeron and a third-round draft pick in 2008. On July 1, 2007, the Oilers signed Grebeshkov to a one-year contract. He started the 2007–08 season on the Oilers' roster and played his first Oilers game against the Detroit Red Wings on October 8, 2007. On February 19, 2008, Grebeshkov scored the 8,000th goal in Oilers history in a 5–4 loss to the Nashville Predators. On July 21, 2009, the Oilers re-signed Grebeshkov to a one-year, $3.15 million contract extension just prior to a scheduled salary arbitration hearing. In the 2009–10 season, Grebeshkov's slow start was exacerbated after he suffered a knee injury during a 3–1 loss to the Buffalo Sabres on November 13, which sidelined him for a month. On March 1, 2010, the Oilers traded Grebeshkov to the Nashville Predators in exchange for a second-round draft pick in 2010. On March 2, he scored a goal in his Predators debut in a 4–3 win, ironically coming against the Oilers. In just his fourth game with the Predators, Grebeshkov took a shot in the groin against the Vancouver Canucks. Though he continued to play following the blocked shot, he required emergency surgery on one of his testicles following the game, causing him to miss the remainder of the regular season. Grebeshkov was cleared to play prior to Game 2 of the Predators' Western Conference Quarter-final match-up against the Chicago Blackhawks. However, he was a healthy scratch for Games 2, 3 and 4 as Predators Head CoachBarry Trotz elected to play rookie Cody Franson in his place. Grebeshkov made his Stanley Cup playoff debut in Game 5, registering two assists in the 5–4 Predators loss. After becoming a free agent on July 1, 2010, Grebeshkov signed a two-year deal with SKA St. Petersburg of the Kontinental Hockey League, four weeks later. He noted that he wanted to stay in the NHL and received several offers, but the offers he received were for 30% to 40% lower than his 2009–10 salary, and he did not want to take that drastic of a pay-cut. On July 18, 2013, after three years of playing in Russia, Grebeshkov returned to the Edmonton Oilers as a free agent, signing a one-year contract. After starting the 2013–14 season with the Oilers, Grebeshkov, however, was unable to cement a role on the team's blueline and was subsequently assigned to Edmonton's American Hockey League affiliate, the Oklahoma City Barons, for the majority of the season. On May 14, 2014, Grebeshkov, as a free agent, opted to return to the KHL, signing a contract with Vityaz Podolsk.
