Короленко улица расположена в Ленинском районе (дома №№ 2-42 и 1-41) и в Октябрьском (четные от дома № 56 и нечетные от дома № 65). Формирование улицы началось в конце 1930-х годов, когда в 10-м квартале Соцгорода были построены двухэтажные жилые дома. Они частично сохранились до настоящего времени по четной стороне в начале улицы, на участке отулицы Московской до улицы Суворова. Название у данной улицы появилось в 1948-1949 годах (документ об утверждении имени улицы не обнаружен). Названа в честь Владимира Галактионовича Короленко (1853-1921), русского писателя и публициста, автора произведений, проникнутых демократическими и гуманистическими идеями. В начале улица застроена двух- и трехэтажными многоквартирными шлакоблочными и кирпичными домами. На участке от улицы Нефтяников до трамвайного управления расположено 2 четырехэтажных и 4 пятиэтажных многоквартирных кирпичных и крупнопанельных жилых домов. За трамвайным управлением в пределах Ленинского района находятся 2 девятиэтажных крупнопанельных жилых дома №№ 41 и 42, построенных в конце XX века. В Октябрьском районе, к северу от улицы Тагильской, находится массив первичной частной застройки одноэтажных деревянных, кирпичных и шлакоблочных домов. В данном месте более 15 лет работал стихийный, внеплановый оптово-розничный овощной рынок, получивший название от улицы Короленко. Частный сектор по нечетной стороне сохранился до улицы Сорокина, а по четной стороне в 1970-е годы был выстроен (дома №№118 -132а) квартал из 13-ти пятиэтажных многоквартирных панельных домов для работников Орского механического завода. Участок улицы Короленко от Сорокина до Волкова застраивался в конце XX века крупнопанельными девятиэтажными жилыми зданиями.