Boumedienne was drafted in the fourth round, 91st overall by the New Jersey Devils in the 1996 NHL Entry Draft. He played in Swedish leagues for the early part of his career before joining the Tappara Tampere of the Finnish Elite League in 1998-99. Boumedienne played two seasons with Tappara, earning a professional career high of 32 points in 50 games during the 1999-00 season. Boumedienne was also an active member of the Swedish national junior team, as he represented Sweden at the 1997 and 1998 World Junior Championships.
Boumedienne made his North American professional debuit with the Devils' AHL affiliate, the Albany River Rats, in 2000-01. In his first professional season in North America, Boumedienne finished second among River Rats defensemen in scoring with 8 goals and 29 assists for 37 points in 79 games. The performance also earned Boumedienne a nomination to the 2001 AHL All-Star Game.
Boumedienne made his NHL debut during the 2001-02 season for the Devils, playing in one game with New Jersey. However, Boumedienne was traded to the Tampa Bay Lightning in mid-season. Boumedienne then spent a majority of the season with Tampa's AHL affiliate, the Springfield Falcons. However, Boumedienne did play in 3 games with Tampa Bay in that year, as well. He finished the 2001-02 season with a single goal. Boumedienne then played 6 NHL games in the 2002-03 season, earning another single goal. During the 2002-03 season, Boumedienne made appearances with the Binghamton Senators and Portland Pirates of the AHL, before earning a spot with the Washington Capitals. In the 2003-04 season, Boumedienne played in a career high 37 NHL games for the Capitals, recording 2 goals and 12 assists.
Due to the NHL lockout of 2004-05, Boumedienne was forced to return to European leagues to play professional hockey. Boumedienne did not return to North American hockey until the 2007-08 season, when he signed with the Toronto Maple Leafs. Boumedienne was sent to the Maple Leafs AHL affiliate, the Toronto Marlies, where he played 52 games in 2007-08, scoring 7 goals and recording 35 assists.
