Тем временем в 1944 году же на нашего героя отправилась в Белоруссию играть в Русском драматическом театре, а Столяров приступил к съемкам в фильме «Кащей Бессмертный». Во время натурных съёмок этого фильма в Барнауле игравший Никиту Кожемяку Столяров едва по-на стоящему не убил Кащея в исполнении Георгия Милляра, который был его астрологическим «родственником» - тоже Скорпионом (7 ноября 1903 года, Скорпион-Кот). В сцене битвы Столяров так рубанул своего «родственника» деревянным мечом по голове, что того увезли в больницу с сотрясением мозга. К счастью, все обошлось и фильм досняли с теми же исполнителями.

В 1946 году Столяров попробовал свои силы в комедии, снявшись в роли денщика в фильме «Старинный водевиль», который снимался на студии «Баррандов» в Чехословакии. Высокое киноначальство понимало желание Столярова выйти из привычного образа «былинного героя» и сыграть что-то иное, однако одобрить его не могло. После войны тема патриотизма продолжала оставаться актуальной в обществе, поэтому Столярову не оставалось ничего иного, как вернуться к прежним своим героям - сильным и смелым людям, не боящимся в одиночку противостоять коварному врагу. Одним из таких фильмов стала картина «Далеко от Москвы» (1950) по одноименному роману В. Ажаева (кстати, очень популярному в то время у читателей), рассказывающая о том, как в годы войны советские люди самоотверженно прокладывали нефтепровод около Красноярска. Столяров играл в фильме роль Рогова, за которую был удостоен (вместе с друг ими создателями фильма) Сталинской премии (1951). Тогда же ему присвоили и звание заслуженного артиста РСФСР.