Bodnarchuk spielte in seiner Jugend für die Halifax Mooseheads in der Ligue de hockey junior majeur du Québec (LHJMQ), nachdem er bereits 2005 mit dem Team Canada Atlantic die Bronzemedaille bei der World U-17 Hockey Challenge gewonnen hatte. Nach seiner ersten Saison in Halifax, in der er ins All-Rookie Team der LHJMQ gewählt wurde, wählten ihn die Boston Bruins im NHL Entry Draft 2006 an 128. Position aus und setzten ihn in der Folge erstmals in den Playoffs der Saison 2006/07 bei den Providence Bruins ein, ihrem Farmteam aus der American Hockey League (AHL). Nach der Spielzeit 2007/08, in der er die Mooseheads als Mannschaftskapitän angeführt hatte, wechselte Bodnarchuk fest in den Kader der Providence Bruins, für die er bis 2012 aktiv war. In diesem Zeitraum, in der Saison 2009/10, debütierte er zudem bei den Boston Bruins in der National Hockey League (NHL) und kam dort auf fünf Einsätze.
Als Free Agent unterzeichnete er im Juli 2012 einen Einjahresvertrag bei den Los Angeles Kings, der nach Ablauf um zwei weitere Spielzeiten verlängert wurde. Jedoch kam der Verteidiger ausschließlich für das AHL-Farmteam der Kings, die Manchester Monarchs, zum Einsatz und gewann mit diesen 2015 den Calder Cup. Im Sommer 2015 schloss er sich, ebenfalls als Free Agent, den Columbus Blue Jackets an, bei denen er sich erstmals im NHL-Kader etablieren konnte und dort auf 16 Einsätze kam. Als er jedoch im Januar 2016 über den Waiver erneut in die AHL geschickt werden sollte, verpflichtete ihn die Colorado Avalanche, wo er bis zum Saisonende 21 Partien bestritt. Trotzdem verlängerte Colorado seinen auslaufenden Vertrag nicht, sodass er im Juli 2016 einen neuen Zweijahresvertrag bei den Dallas Stars unterzeichnete.
(Legende zur Spielerstatistik: Sp oder GP = absolvierte Spiele; T oder G = erzielte Tore; V oder A = erzielte Assists; Pkt oder Pts = erzielte Scorerpunkte; SM oder PIM = erhaltene Strafminuten; +/− = Plus/Minus-Bilanz; PP = erzielte Überzahltore; SH = erzielte Unterzahltore; GW = erzielte Siegtore; 1Play-downs/Relegation; Kursiv: Statistik nicht vollständig)