Первый договор о сотрудничестве между городами-побратимами Кривой Рог и Нижний Тагил был заключён 12 августа 1994 года. Но начало этой дружбе положено в годы Великой Отечественной войны, когда тагильские и криворожские предприятия общими усилиями в тылу ковали оружие Победы.
Летом 1941 года гитлеровцы рвались к Кривому Рогу, а 7 августа в город поступило телеграфное распоряжение наркома тяжелой промышленности И.Ф. Тевосяна об остановке одного из крупнейших предприятий черной металлургии - завода «Криворожсталь» и эвакуации его на Урал - на новотагильский металлургический завод. В Нижний Тагил эвакуировали оборудование, рабочих и членов их семей. Многие не имели теплой одежды, не было запаса продовольствия. Местные жители делились с эвакуированными всем.
Большинство криворожан влилось в ряды рабочих НТМЗ. Они работали в самых ответственных цехах: доменном, мартеновском, прокатном. Весомый вклад криворожские металлурги внесли в строительство и освоение домны №3 весной 1944 года. За разработку и освоение технологии выплавки феррохрома криворожским доменщикам Л. Шумакову и В. Герасимову была присвоена Государственная премия, Ф.А. Хилькевичу было присвоено звание Героя Социалистического Труда. Приумножали славу Нижнего Тагила горняки Криворожья. Вошли в историю города шахтеры Семиволос, Завертайло, Еременко, Головатый, маркшейдер Гриненко.
После освобождения Украины из Нижнего Тагила были отправлены 730 вагонов с оборудованием и более 4000 тагильчан переехали жить и трудиться в Кривой Рог. В течении последующих десятилетий жители двух городов сохраняли теплые и дружественные связи, зародилось много общих традиций.
12 августа 1994 года был заключен первый договор о дружбе и сотрудничестве между городами Кривой Рог и Нижний Тагил, в соответствии с которым им был присвоен статус городов-побратимов.