С апреля 1997 года Николай Аксененко занимал должность министра путей сообщения, на которой подготовил концепцию реформы отрасли. В 1998 году он впервые объявил о создании частных операторских компаний, выступил с инициативой продолжения строительства БАМа и предложил возродить проект по соединению Сахалина с материком тоннелем.
В мае 1999 года, после отставки правительства Евгения Примакова, господин Аксененко считался основным кандидатом на пост премьер-министра. СМИ называли его доверенным лицом президентской семьи и человеком Березовского. В телефонном разговоре со спикером Госдумы Борис Ельцин даже пообещал представить его кандидатуру, но в последний момент изменил решение и предложил Сергея Степашина. В новом правительстве господин Аксененко получил пост первого вице-премьера. 16 сентября 1999 года он был переназначен главой МПС и первым вице-премьером в кабинете Владимира Путина.
В том же году Николай Аксененко назывался в СМИ одним из главных претендентов на президентский пост, но ставший преемником господин Путин уже в январе 2000 года лишил главу МПС статуса вице-премьера. После этого господин Аксененко занялся созданием РАО "Российские железные дороги". Финансовые потоки, которые он тогда контролировал, оценивались экспертами в $10 млрд в год.
В октябре 2001 года министру предъявили обвинения в превышении полномочий. Обвинения касались незаконной траты на содержание центрального аппарата МПС прибыли железных дорог, перечисленной в ведомственные фонды образования и здравоохранения. Ущерб государству оценивался в 20 млрд руб. 3 января 2002 года господин Аксененко был уволен.
В октябре 2003 года одновременно с передачей дела в суд страдавшему лейкозом Николаю Аксененко разрешили выехать на лечение в Германию, где он скончался 20 июля 2005 года.