Родом из совершенно не хоккейного казахстанского города Павлодар, где первый крытый ледовый дворец был открыт только в октябре 2003 года. Тем не менее Максим Кузнецов является одним из лучших казахстанских хоккеистов последних лет и лучшим защитником из Казахстана за все время выступления спортсменов родом из этой страны в сильнейшей профессиональной лиге мира НХЛ.
По количеству матчей (136) проведенных в Национальной хоккейной лиге занимает 3 место среди казахстанцев, после нападающего Николая Антропова и вратаря Евгения Набокова. Также Максим Кузнецов занимает 3 место по количеству матчей за Detroit Red Wings (117) среди защитников из постсоветских стран, после Владимира Константинова и Вячеслава Фетисова.
Максим Кузнецов является ярко выраженным игроком оборонительного плана с большими габаритами, играющим в жесткий силовой хоккей, поэтому он имеет невысокие показатели по набранным очкам.
Начинал играть в детско-юношеской хоккейной секции «Восход» в Павлодаре, «домашней ареной» которой была открытая хоккейная коробка в одном из спальных районов промышленного северо-казахстанского города. Затем последовал переезд в Усть-Каменогорск - в школу местного Торпедо, а спустя некоторое время Максим Кузнецов оказался в школе московского «Динамо». Приглашался в юношескую сборную СНГ. На высшем уровне в российском чемпионате дебютировал в 17-летнем возрасте в сезоне 1994-1995 годов, и в составе «Динамо» (Москва) стал победителем первенства Межнациональной хоккейной лиги.
По окончании дебютного профессионального сезона Максим Кузнецов стал первым выходцем из Казахстана, которого выбрали в первом раунде драфта НХЛ. Под общим 26 номером его зарезервировала одна из ведущих команд Национальной хоккейной лиги — Detroit Red Wings.
Сыграл первый матч в регулярном сезоне НХЛ 17 октября 2000 года в составе Detroit Red Wings против St. Louis Blues. А 16 декабря 2000 года забросил первую шайбу также в поединке против St. Louis Blues.
В сезоне 2001-02 года Кубок Стэнли завоевал Detroit Red Wings в составе которого Максим Кузнецов был игроком основного состава в регулярном чемпионате, правда в играх плей-офф Кубка Стэнли Максим не участвовал.
11 марта 2003 года был обменян из Detroit Red Wings в Los Angeles Kings вместе с Шоном Эйвери и правами выбора в первом и втором раундах драфта на Мэтью Шнайдера. Однако в составе "Королей" Кузнецову закрепиться не удалось. За калифорнийскую команду Максим сыграл только 19 встреч. Последний матч в Национальной хоккейной лиге защитник провел 31 декабря 2003 года против Phoenix Coyotes.
Всего за время выступления в НХЛ Максим Кузнецов провел 136 матчей, в которых забил 2 гола и сделал 8 голевых передач (10 очков), набрал 137 минут штрафа, показатель полезности ?5.
Также он сыграл 206 матчей в Американской хоккейной лиге, забил 10 голов, сделал 27 голевых передач (37 очков), набрал 176 минут штрафа. В плей-офф АХЛ на счету Кузнецова 10 игр, 1 результативная передача (1 очко), 8 штрафных минут.
Всего в североамериканских хоккейных лигах Максим выходил на лед в 352 встречах, и именно за океаном прошла большая часть его карьеры профессионального игрока.
7 июня 2004 во время локаута в НХЛ подписал контракт с московским «Динамо», которое в сезоне 2004/2005 стало чемпионом России. Затем играл за питерский СКА, омский «Авангард» и чеховский «Витязь». Весной 2008 года подписал контракт с челябинским «Трактором», но из-за травм сыграл в сезоне 2008/2009 всего 10 матчей. После чего завершил спортивную карьеру.
В регулярных чемпионатах России Максим Кузнецов выходил на лед в 153 встречах, забил 8 голов, сделал 12 голевых передач (20 очков), набрал 279 минут штрафа. В играх плей-офф чемпионатов России провел 7 матчей, очков за результативность не набирал, штрафных минут 4.