Занятиями по боксу он увлёкся в позднем возрасте 20 лет, в качестве тренера выступал Олег Шалаев. Дебютировал Валуев на профессиональном ринге в 1993 году в Германии, когда сражался с Джоном Мортеном. Во втором раунде Николай нокаутировал соперника и тем самым вышел победителем в бою. Спустя 6-ть лет в 1999 году рослый спортсмен завоёвывает титул чемпиона России по боксу, а в 2000-ом становится чемпионом мира по версии Пан-Азиатской-Боксерской Ассоциации.
В новом тысячелетии у Валуева появляется новый тренер, теперь им является Манвел Оганесович Габриэлян. В 2004 году, выступая на ринге против Ричарда Банго, Валуев берёт вверх над нигерийцем, победив техническим нокаутом в 6-ом раунде. С этого момента боксёр становится чемпионом среди профессионалов по версии ВБА. В следующем году происходит бой между Валуевым и Ларри Доланьдом, в котором русский боксёр снова побеждает, отправив соперника в нокаут уже в третьем раунде. Вскоре Валуев боролся за титул WBA в супертяжёлом весе против Ларри Дональда. В тяжёлом бою Николаю удалось выиграть, хотя зрители посчитали решение судей необъективным.
После очередной победы Валуева, 17 декабря 2005 года он забирает у Джона Руиса титул чемпиона мира среди профессионалов в супертяжёлом весе по версии ВБА. В 2006 году Николай удачно защищает свой пояс, одолев Оуэна Бека техническим нокаутом. В октябре того же года боксёр в очередной раз доказывает что он достоин титула чемпиона, победив Монте Барретта. Вскоре соперником Николая Валуева вызвался боксёр из Узбекистана Руслан Чагаев. На протяжении всего боя претендент доминировал, благодаря чему по очкам победу одержал Чагаев.
Летом 2008 года Валуев и Джон Руис снова встречаются на боксёрском поприще. Победителю должен был достаться вакантный титул WBA среди тяжеловесов. И в этот раз россиянин выиграл.
