Сергей Столяров родился 1 ноября 1911 года в деревне Беззубово Тульской губернии в семье лесника Дмитрия Столярова. У Сергея было еще три брата и сестренка. Жили они хоть и бедно, но дружно. Отца своего Сергей практически не помнил. В 1914 году началась первая мировая война. Рекрутов набирали по жребию. Идти на фронт тогда выпало одному богатому крестьянину, но он обратился к своим землякам: мол, тот, кто пойдет на фронт вместо него, получит избу, лошадь и корову. Это было настоящее богатство, отказаться от которого было не всякому под силу. Вот отец Столярова и согласился на такую замену. Он ушел на фронт и был убит во время газовой атаки. Обещанное богатство его семья получила, однако радовалась ему недолго. Октябрьская революция все у них конфисковала. Семья Столяровых осталась без средств к существованию. В деревне начался голод, и, чтобы спасти своих детей, мать решила младших оставить у себя, а троих старших сыновей отправить в Ташкент. В те годы этот город называли хлебным. Так начались скитания Сережи Столярова по объятой войной России. В Ташкент тогда он так и не попал — заболел брюшным тифом, и братья оставили его в больнице в Курске, а сами так и пропали в водовороте тех событий. Сергей вылечился и некоторое время оставался в больнице, до полного выздоровления, помогал санитарам. Затем его определили в курский детский дом. Именно там он впервые и узнал, что такое театр. Воспитатель организовал из детдомовских ребят драмкружок.

В конце 20-х годов Столяров закончил Первое профтехучилище в Москве и одно время работал паровозным машинистом на Киевской железной дороге. В свободное время он учился в театральной студии для рабочих при МХАТе, организованной актером Алексеем Диким. Актерские способности у Столярова, без сомнения, были, поэтому по окончании студии ему посоветовали поступать во МХАТ. В 1932 году, на приемных экзаменах в знаменитом театре Столяров читал монолог Нила из пьесы М. Горького "На дне". Читал прекрасно, члены высокой комиссии, а это были К. Станиславский, В. Немирович-Данченко, В. Мейерхольд — приняли решение из пятисот абитуриентов зачислить в театр только двоих. Одним из них был Сергей Столяров, другим — Михаил Названов.

Между тем в начале 30-х годов удачно складывалась не только творческая жизнь Столярова, но и личная. В 1930 году его призвали на военную службу, и он был распределен в Театр Советской Армии. Там он и познакомился с молодой актрисой Ольгой Константиновой (она только что закончила театральные курсы Ю. Завадского). Она вспоминает: "Из-за моей учебы откладывалась свадьба. Сережа делал предложения, а я решительно отказывала — мол, я артистка, замуж не хочу выходить. Ссорились отчаянно…

Свадьбы, конечно, у нас никакой не было, в 1931 году их не играли. Погрузил муж на саночки всю мою собственность, и мы поехали в его комнату девять метров, без печки, без особой мебели. К моей маме ездили обедать… До сих пор помню, что у нас было: столик, тахта, книжки, даже шкаф отсутствовал…"

Тем временем зачисленный в труппу МХАТа Столяров некоторое время играл "на подхвате" — у него была маленькая роль в спектакле «Воскресение» по Л. Толстому. Играл он конвойного, охранявшего Катю Маслову. Так продолжалось два года. В 1934 году молодого актера заметил режиссер Александр Довженко и пригласил на эпизодическую роль летчика в своем фильме «Аэроград». Так состоялся дебют Столярова в кино. Дебют был удачным: статный красавец Столяров не мог не привлечь к себе внимания. Так оно и произошло. В 1936 году сам Г. Александров без всяких проб пригласил актера на главную роль в своем новом фильме «Цирк». С этой картины и началась звездная слава киноактера Сергея Столярова. Его лицо улыбалось с огромных рекламных плакатов, мелькало в газетах и журналах (кстати, именно благодаря этому фильму его после 18 лет разлуки нашли мать и брат Роман). Однако это было «парадное» лицо актера Столярова. То, что внутри этого 24-летнего красавца происходит драма, связанная с репрессиями 1937 года, знали немногие. А ведь тот год начинался для Столярова радостно. Сначала он стал отцом: 28 января у них с Ольгой родился сын, которого назвали Кириллом (в дальнейшем он пойдет по стопам отца и с 1956 года будет сниматься в кино). Затем должна была состояться торжественная премьера фильма «Цирк». Однако Столяров идти на нее отказался. Что же произошло? Послушаем рассказ сына актера — К. Столярова: "Еще до премьеры фильма «Цирк» получил самую высокую оценку «наверху». А накануне премьеры расстреляли изумительного оператора Владимира Семеновича Нильсена. В те годы подавались расстрельные списки. Расстреливало НКВД, но "кандидатуры"-то подбирались на местах! Раздавался звонок: "У вас есть троцкисты?" Да как не быть троцкистам в самом советском искусстве?! Например, Нильсен. Почему он? Да фамилия у него странная, к тому же жена — балерина и вдобавок ко всему итальянская подданная. Отец был потрясен гибелью Нильсена. А вокруг все готовились к премьере «Цирка». Специально закупили аппаратуру в Америке, в Парке культуры имени Горького открыли летний кинотеатр. Составляли наградные списки, будто ничего не произошло. И отец не пошел на премьеру, куда пригласили только исполнителей главных ролей. Он не получил орденок и не стал холуем. Кем он был тогда? Мальчишкой 24 лет! Но он не боялся. Чего бояться в своей стране?! Фильм с триумфом прошел по экранам страны. Возможно, всенародная любовь, «заметность» спасли отцу жизнь… За фильм «Цирк» отец получил только зарплату.