Construction of the station began shortly after the launch of the second stage in 1938. Despite the World War II the station was opened on time. Later in 1978 the platform was lengthened. This part is in a more modern style than the rest of the station.
The station honors the Soviet fighting men with its heavy ornamentation. The architects, I. Taranov and N. Bykova, won a USSR State Prize for their design.
The decorations include seven octagonal ceiling mosaics by V. Frolov on the theme of wartime industry and bas-reliefs running along the base of the ceiling (by artists N.V. Tomsky, A.E. Zelensky, S.M. Rabinovich, and N.M. Shtamm) depicting the soldiers of the Red Army in combat. The pink and white marble pylons are also decorated with cast-bronze portraits of Russian war heroes like Mikhail Kutuzov and Alexander Nevsky. The ornate marble benches lining the platform were removed from the original Cathedral of Christ the Saviour before it was demolished. Floor lamps, long since replaced with more up-to-date lighting in other Metro stations, still give Novokuznetskaya an atmosphere of brooding shadow.
Novokuznetskaya's round entrance vestibule is located off Pyatnitskaya Street, north of the intersection with Klimentovsky Street.