Лишившись возможности сниматься на «Мосфильме», Столяров стал одним из самых востребованных артистов на «Союздетфильме». В те годы на волне патриотизма, которая стала нарастать в стране примерно с 1936 года, в советском кинематографе стали появляться фильмы, должные этот патриотизм всячески пропагандировать. В итоге на свет стали по являться экранизации русских народных сказок, где былинные герои расправлялись с полчищами врагов и завоевывали сердца первых красавиц. И лучшего актера в советском кино, чем Сергей Столяров - а он был статным красавцем с типичными чертами русского былинного богатыря, - и невозможно было себе представить. И вот уже в конце 30-х на экраны страны один за другим выходят фильмы-сказки с участием Столярова: «Руслан и Людмила» (1939; главная роль - Руслан) и «Василиса Прекрасная» (1940; главная роль - Иванушка). Последний фильм снял Александр Роу, который в 1944 году вновь пригласил Столярова в свою новую картину «Кащей Бессмертный» - на роль Никиты Кожемяки.

Отметим, что Роу родился в год Лошади (1906), а та Свинье, как уже говорилось, плохой товарищ. Однако по месяцу рождения великий режиссер-сказочник был Рыбами (8 марта), а они из одной стихии со Скорпионом - Вода. Именно эта «водность» и скрепляла творческий союз режиссера и актера.

Помимо сказочных героев Столяров в те же годы играл и роли своих современников - таких же смелых и бесстрашных русских людей, как и его былинные персонажи, - в фильмах «Моряки» (1939) и «Гибель «Орла» (1940; главная роль - Федор Чистяков).