Oduya's first club was Hammarby IF, where he played as a junior. In 2000, at the age of 19, he moved to North America to play in the Quebec Major Junior Hockey League (QMJHL). He spent one season in North America, splitting time between Victoriaville Tigres and Moncton Wildcats. After moving back to Sweden, he played two seasons with Hammarby's pro-team in HockeyAllsvenskan before signing a contract with Djurgårdens IF in the Swedish Elitserien. During the two seasons he spent with the team, he was known as an aggressive defenceman and an enforcer. At times, he fought with opposition players and registered high penalties in minutes numbers. Despite this, he was also a dependable player and played regularly in the Swedish national team during the Euro Hockey Tour. In the 2005–06 season, after he had been dismissed by the Washington Capitals, the NHL organization that drafted him 221st overall in 2001, he moved to another Swedish team, Frölunda HC. With Frölunda, he played as a more offensive defenceman, scoring eight goals and 11 assists.
The following season, 2006–07, Oduya signed with the New Jersey Devils in the NHL. Although expected by many to be a depth player with the Devils, when several of the team's defenders were injured, Oduya earned a spot in the lineup. He played surprisingly well in the NHL, periodically registering nearly 20 minutes of ice time per game. He played in 76 Devils games that season, only missing eight due to a mid-season injury. However, in the 2007 Stanley Cup playoffs, he was not dressed for New Jersey when the Devils were defeated in the second round, largely due to the impressive play of rookie defenceman Andy Greene. After several successful NHL seasons, Oduya was named to the Swedish roster for the 2010 Winter Olympics in Vancouver.
On 4 February 2010, he was traded to the Atlanta Thrashers, along with Niclas Bergfors, Patrice Cormier and a first-round draft pick in 2010, in exchange for Ilya Kovalchuk and Anssi Salmela. Oduya skated for the team during it's inaugural season after moving to Winnipeg, Manitoba to become the Winnipeg Jets.
On 27 February 2012, Oduya was traded to the Chicago Blackhawks for a second- and third-round pick in 2013.
In October 2012, during the 2012–13 NHL lockout, Oduya traveled to Bangkok, Thailand, to play for the local Flying Farangs team in the 18th Annual "Land of Smiles" Hockey tournament. He carried his team to the championship against Abu-Dhabi, and helped bring home Bangkok's first title in tournament history.
In June 2013, Oduya won his first Stanley Cup with the Chicago Blackhawks, who defeated the Boston Bruins in six games in the Finals. In Game 6 of the Stanley Cup Finals, Oduya assisted on the Cup winning goal scored by Dave Bolland. Oduya's shot came from the left point and deflected off the stick of Michael Frolík. Bolland, in position in front of the Boston goal, pushed the deflected shot past Bruins goaltender Tuukka Rask to give the Blackhawks their second Stanley Cup in four years.
On 15 June 2015, at the United Center in Chicago, Oduya won his second Stanley Cup with the Chicago Blackhawks over the Tampa Bay Lightning in six games. It was the Blackhawks' third Stanley Cup in six years.
After four seasons with the Blackhawks, Oduya left as a free agent and signed a two-year contract with the Dallas Stars on 15 July 2015. Blackhawks teammate Patrick Sharp also joined the Stars a few weeks earlier via trade.
In the final year of his contract with the Stars in the 2016–17 season, Oduya was traded back to Chicago in exchange for Mark McNeill and a conditional fourth-round draft pick on 28 February 2017. He played out the season with the Blackhawks appearing in 15 regular season games for 1 goal and 1 assist.
As a free agent, having left the Blackhawks for a second time, Oduya agreed to a one-year bonus ladened contract with the Ottawa Senators on July 24, 2017.
Johnny is the son of a Kenyan father and a Swedish mother. He is the younger brother of the late Fredrik Oduya, a former NHL draftee who was an enforcer in the minor leagues.