El primer assentament està datat el 1763 amb la creació d'un poble anomenat Koltxuguino. L'extracció de carbó va començar el 1870, tot i que no fou intensiva fins al 1912. La població va ser batejada amb el nom de Léninsk el 1922 i el 1924 amb el seu nom actual, Léninsk-Kuznetski. El 1925 va adquirir l'estatus de ciutat.