В 1618 г. основан укреплённый Кузнецкий острог на левом берегу р. Кондома, недалеко от её впадения в Томь. В 1620 г. перенесён на высокий правый берег Томи.

Название обусловлено тем, что среди коренных жителей этих мест, северных шорцев, было распространено кузнечное дело: они добывали и плавили руду, ковали из железа утварь и оружие. В русских документах 17 в. они именуются кузнецкими людьми или кузнецкими татарами, а район их проживания - Кузнецкой Землёй. Выросший из острога населённый пункт именовался Кузнецк или Кузнецк-Сибирский для отличия от города Кузнецк Пензенской губернии.

С 1622 г. - город Кузнецк, входящий в Бийскую сторожевую линию, защищавшую пограничный район Южной Сибири от набегов киргизских и джунгарских ханов. Сюда после восстаний 1648 и 1682 гг. были сосланы московские стрельцы. С 1804 г. - центр Кузнецкого округа Томской губернии. В 1846 г. крепость упразднена.

В 1912 г. образовалось АО "Копикуз", которое ставило перед собой задачу разработку угольных месторождений Кузбасса, в 1913 г. была проложена ж.д. ветка. Ж.д. станцию поставили на левом берегу, станцию назвали Кузнецк, возникший пристанционный посёлок в 1914 г. получил название Сад-город.

В 1929 г. началось строительство Кузнецкого металлургического комбината под руководством академика И.П. Бардина (1883-1960) и по проекту американской фирмы "Фрейн". Первая очередь комбината была сдана в эксплуатацию в 1932 г.

Сталинская индустриализация СССР превратила в 1930-е город в важный угледобывающий и промышленный центр. Именно Новокузнецку посвящено известное стихотворение Маяковского «Рассказ товарища Хренова…» («Я знаю — город будет, Я знаю — саду цвесть, Когда такие люди, В стране Советской есть»).

7 января 1929 г. Сад-город отнесён к категории рабочих посёлков.
С 3 июля 1931 г. - город Новокузнецк. В 1931 г. в нём проживало 45.0 тыс. жителей. 2 марта 1932 г. к городу Новокузнецку был присоединён город Кузнецк (тогда назывался Кузнецк-Сибирский).
25 мая 1932 г. объединённый город получил название Сталинск.

В 1941 были пущены эвакуированные Новокузнецкий алюминиевый завод и Кузнецкий завод ферросплавов. Всего пущено 7 заводов. Кузнецкий Металлургический комбинат выпускал военную продукцию, из стали КМК были сделано несколько танковых соединений. Завод №526 дал фронту 80 тыс. ручных пулемётов.

В 1960-х гг. построен Западно-Сибирский металлургический комбинат.
С 1961 г. - город Новокузнецк. День города отмечается 3 июля.