К сожалению, и третья попытка Солоницына добиться успеха в стенах прославленного учебного заведения закончилась плачевно. Но тут на помощь старшему брату пришёл младший. В очередном письме он сообщил ему о том, что при Свердловском драматическом театре открылась студия, на экзамены в которую Анатолий вполне может успеть. Тот принял это предложение и оказался прав. В отличие от столичных педагогов, провинциальные оказались гораздо проницательнее, потому что углядели в молодом абитуриенте несомненный талант и приняли его в своё заведение.
Свердловская жизнь братьев Солоницыных была насыщена до предела. Несмотря на то что занятия отнимали у них массу сил и энергии, они вечерами вынуждены были работать грузчиками или сколачивать ящики на кондитерской фабрике. Кроме этого у Анатолия хватало сил выступать со стихами на различных молодёжных вечерах.
В конце 50-х из Фрунзе братьям пришло печальное известие — их отца исключили из партии и выгнали с работы. Причиной этого были следующие события. Под впечатлением 20-го съезда партии отец и несколько его приятелей в нерабочее время собирались на одной из квартир и устраивали жаркие дискуссии о культе личности. Видимо, один из участников этих дискуссий оказался стукачом, и вскоре об этих посиделках стало известно компетентным органам. Всех «заговорщиков» строго наказали. К счастью, длилось это недолго, и уже в 1960 году справедливость восторжествовала — Солоницына-старшего восстановили в партии.
Между тем в июне того же года Анатолий закончил театральную студию и был зачислен в труппу Свердловского драмтеатра. За год переиграл массу различных ролей, однако в основном это были маленькие роли, ни одна из которых не принесла ему настоящего удовлетворения. Исключением была лишь роль Героя в пьесе Н. Погодина «Цветы живые». Так продолжалось около четырёх лет.
1965 год круто изменил судьбу Солоницына. В том году судьба свела его с двумя режиссёрами, которые во многом определили его дальнейшую творческую судьбу. Речь идёт о Глебе Панфилове и Андрее Тарковском.
Первый тогда работал режиссёром свердловского телевидения и приступал к работе над телефильмом «Дело Курта Клаузевица». На главную роль — немецкого солдата Курта Клаузевица — он пригласил именно Солоницына. Это была первая роль актёра вне стен драматического театра.
С Тарковским Солоницын познакомился при следующих обстоятельствах. В журнале «Искусство кино» был напечатан сценарий будущего фильма «Андрей Рублёв». Прочитав его, Солоницын настолько загорелся желанием сыграть главную роль, что надумал немедленно ехать в Москву и самому проситься на роль.
Когда была сделана первая кинопроба с ним, единственным человеком, который увидел в этом актёре Андрея Рублёва, был Тарковский. Все остальные участники съёмок категорически отказывались верить в успех Солоницына. Чтобы переубедить их, Тарковскому пришлось сделать ещё две кинопробы, но даже после этого мнение его оппонентов не изменилось. Сам Михаил Ромм убеждал Тарковского отказаться от своего решения снимать Солоницына в главной роли, не говоря уже об остальных членах художественного совета «Мосфильма». Но режиссёр упрямо стоял на своём. Когда ситуация достигла критической точки, Тарковский решил использовать последний шанс. Он взял фотографии двух десятков актёров, снимавшихся в пробах к «Рублёву», и отправился к реставраторам, специалистам по древнерусскому искусству. Разложив перед ними эти фотографии, он попросил выбрать из них актёра, наиболее соответствующего образу великого художника. И все опрашиваемые дружно указали на Анатолия Солоницына. Так были рассеяны последние сомнения на этот счёт. В апреле 1965 года Солоницына официально утвердили на роль Андрея Рублёва.
Съёмки фильма начались 8 мая во Владимире и продолжались с перерывами около года. Солоницын настолько был увлечён ролью, что решил оставить театр — он написал заявление об увольнении. Многие тогда отговаривали его от этого шага, убеждали оставить для себя пути к отступлению (вдруг его кинематографическая карьера не удастся), но он не внял этим советам. И его можно было понять: в 1966 году к нему поступило сразу два предложения от кинорежиссёров: Г. Панфилов утвердил его на роль комиссара Евстрюкова в фильме «В огне брода нет», а Лев Голуб — на роль командира продотряда в «Анютиной дороге».
Тем временем судьба «Андрея Рублёва» складывалась драматично. Когда работа над ним была завершена и картину посмотрело высокое кинематографическое начальство, его охватила настоящая паника. По их мнению, фильм был чрезвычайно перенасыщен сценами жестокости и пропитан откровенным духом религиозности. Того же мнения были и партийные сановники из ЦК. Но финальную точку в этой дискуссии поставили не они, а руководитель ГДР Вальтер Ульбрихт. Он тогда приехал в Москву с официальным визитом, и на Воробьёвых горах ему устроили просмотр последних новинок советского кино. Среди них оказался и «Андрей Рублёв». После его просмотра Ульбрихт изрёк всего лишь одну фразу, однако её вполне хватило, чтобы на несколько лет положить фильм на полку. А фраза его звучала так: «Это — антирусский фильм!»
Между тем эпопея с запретом фильма заметно сказалась на умонастроении Солоницына. Он вдруг ясно осознал шаткость своего положения в мире кино, где у него уже появились первые противники. Причём не только в высоких киношных кабинетах, но и внизу — кое-кто из столичных актёров откровенно недолюбливал провинциала, перебежавшего им дорогу. Отсюда и итог: за последующие два года ему не поступило ни одного серьёзного предложения сняться в кино. Что касается фильма «Один шанс из тысячи», в котором Солоницын снялся в 1968 году, то отнести его к серьёзным работам никак нельзя — фильм по своим художественным качествам был откровенно слабый. Сняться в нём (а Солоницын играл главную роль — советского разведчика Мигунько) его подвигло только то, что создавали картину его друзья: художественным руководителем постановки был А. Тарковский, режиссёром — Левон Кочарян. В прокате 1969 года фильм занял 19-е место, собрав 28,6 млн. зрителей.
Солоницын решил вновь вернуться в Свердловский театр. (Стоит отметить, что к тому времени он уже был женат, у него родилась дочка Лариса.) Однако серьёзных ролей в родном театре ему не давали, поэтому в конце 1968 года он на время уехал в Новосибирск, где в театре «Красный факел» ему предложили сыграть пушкинского Бориса Годунова.
Тем временем с мёртвой точки сдвинулась судьба «Андрея Рублёва». 18 февраля 1969 года состоялась премьера фильма в Доме кино, а через несколько месяцев после этого картину отправили на Каннский кинофестиваль. Правда, выставили его не в конкурсе, а всего лишь на общественный просмотр и на кинорынок. Однако успех фильма был грандиозным. Международная организация кинопрессы сразу же присудила ему приз. После этого «Совэкспортфильм» сумел заключить ряд выгодных сделок по продаже фильма за рубеж.
