Город Коламбус, штат Огайо, стал официальным домом для будущей команды НХЛ 25 июня 1997 года, когда лига объявила об очередном расширении и включении команд из Атланты, Нэшвилла, Коламбуса и Миннесоты.
Владелец нового клуба, Джон Макконнел, 11 ноября 1997 года объявил, что команда будет носить имя «Блю Джекетс» («Синие Пиджаки»). Первым генеральным менеджером был назначен бывший тренер «Флориды Пантерз» Дуг Маклин. Первым тренером стал Дэйв Кинг.
«Блю Джекетс» дебютировали в НХЛ в сезоне-2000/01, показав достойный результат. Второй сезон получился менее удачным, хотя вряд ли кто-то ждал от «Синих мундиров» выхода на более высокие позиции.
По ходу сезона-02/03 неудовлетворённый игрой команды Маклин уволил с поста тренера Дэйва Кинга и сам занял его место. «Блю Джекетс» заиграли более результативно, но провалы в обороне снова предопределили клубу место среди аутсайдеров НХЛ.
В сезоне-03/04 в составе «Коламбуса» на ведущие позиции вышел Рик Нэш, ставший совладельцем Трофея Мориса Ришара, забив 41 гол. Так же удачно вписался в команду новичок Николай Жердев, однако «Блю Джекетс» по итогам регулярного чемпионата снова оказались в подвале турнирной таблицы.
