В 1959 году Демьяненко закончил институт (на дипломе играл судебного пристава в «Тартюфе») и был приглашен режиссером Андреем Гончаровым в Театр имени Маяковского. Предложение это он принял с радостью, так как не каждому выпускнику выпадало счастье остаться и работать в Москве. В том же году он снялся в небольшой роли в комедии Г. Липшица «Катя-Катюша».

1960 год можно назвать переломным в актерской и личной судьбе Демьяненко. Во-первых, именно тогда он снялся в одной из лучших своих «серьезных» картин и, во-вторых, перебрался жить в Ленинград. Однако расскажем все по порядку.

За несколько месяцев работы в Театре имени Маяковского Демьяненко так и не сумел обрасти серьезными ролями и откровенно скучал. Поэтому, когда хорошо знакомые ему режиссеры А. Алов и В. Наумов предложили ему сняться в очередной своей картине, он согласился не раздумывая, тем более что это была одна из главных ролей — младший лейтенант Ивлев в фильме «Мир входящему».

Картина вышла в 1961 году, можно смело сказать, благодаря случайности. Руководство Госкино в процессе всей работы над фильмом вносило в него всевозможные поправки, резало фильм по-живому, и в какой-то момент вообще хотело его закрыть. Но этого, к счастью, не случилось. Правда, начальники на нем все равно отыгрались. Было сделано всего 370 копий картины, и в основном их прокатывали в провинции. В прессе не было опубликовано ни одного положительного отзыва на нее, зато отрицательных появилось в избытке. В одной из статей, например, фильм обвинили в «экспрессионистической неправде на тему войны».

В то же время на Западе фильм «Мир входящему» получил диаметрально противоположные отзывы. На фестивале в Венеции в 1961 году он получил сразу две награды: «Золотую медаль» и «Золотой кубок» (премия Пазинетти за лучший иностранный фильм). Так имя Александра Демьяненко впервые громко прозвучало на весь кинематографический мир.

Почти одновременно с «Миром входящему» на экраны страны вышли еще две картины с участием нашего героя. На этот раз это были произведения легкого жанра: мелодрама с элементами комедии «Карьера Димы Горина» (реж. Ф. Довлатян и Л. Мирский) и комедия «Взрослые дети» (реж. В. Азаров). В отличие от «Мира…, эти фильмы не имели никаких нареканий со стороны высокого начальства, успешно вышли в прокат и собрали хорошую кассу: первую картину посмотрели 21 млн. зрителей, вторую (в 1962 году) — 28,7 млн. Так имя актера Александра Демьяненко стало широко известно в Советском Союзе.

Тем временем жизнь в столице для нашего героя становилась все более в тягость. Прописки у него так и не появилось, и ему вместе с молодой женой (с нею он познакомился еще в юности, когда играл в драмкружке свердловского Дворца пионеров) приходилось ютиться по чужим углам. Неизвестно сколь долго это могло бы продолжаться, если бы Демьяненко не предложили переехать в Ленинград и работать в штате «Ленфильма». Более того, чтобы у молодого актера не оставалось никаких сомнений, в «колыбели революции» ему выделили квартиру и сразу же предложили главную роль в очередной картине (это был фильм Владимира Венгерова «Порожний рейс»).

За период с 1961 по 1965 год Демьяненко снялся на разных киностудиях в нескольких картинах, однако лишь три из них можно записать в актив его удач: комедия-сказка «Каин XVIII» (1963), приключенческий фильм «Сотрудник ЧК» (1964, 5-е место в прокате — 32,1 млн.