И действительно, в 1959 году он поставил фильм «Трижды воскресший», который рассказывал… о судьбе волжского буксира «Орленок». Фильм с треском провалился, несмотря на то что в главной роли в нем снялась первая красавица экрана тех лет Алла Ларионова.

Этот провал удручил Гайдая, но не настолько, чтобы из-за него бросить кинематограф. И тут в его судьбу вновь вмешался И. Пырьев. В 1960 году он прочитал в «Правде» стихотворный фельетон С. Олейника «Пес Барбос» и тут же предложил Гайдаю снять по нему короткометражный фильм. Он же посоветовал ему взять на роль Бывалого вместо Михаила Жарова актера Евгения Моргунова. (Клички своим героям Гайдай придумал сам: в фельетоне действовали безликие два Николы и Гаврила.) Вторым стал Георгий Вицин, а третьим был намечен Сергей Филиппов. Однако того тогда в Москве не оказалось, и тогда Вицин заявил: «Я вчера был в цирке и видел клоуна — потрясающий парень, как глиста, изумительно одетый». Этим человеком был Юрий Никулин. Вот что он вспоминает: «Гайдай не произвел на меня впечатления комедийного режиссера. Мне тогда казалось, что если человек снимает комедию, то должен непременно и сам быть весельчаком… А передо мной стоял совершенно серьезный человек».

Фильм «Пес Барбос и необычный кросс» вошел в киносборник «Совершенно серьезно» вместе с короткометражкой Э. Рязанова «Как создавался Робинзон». Однако, в отличие от рязановского фильма, «Пес Барбос» имел оглушительный успех у зрителей (его купили более 100 стран).

Стоит отметить, что у актера Е. Моргунова есть особый взгляд на этот фильм, который я здесь и приведу. Вот его слова:

«Это не Леонид Гайдай сделал эту картину. Ее сделал величайший кинорежиссер Иван Александрович Пырьев… Он посмотрел отснятый материал и сказал: «Ленечка, милый мой, хороший, будущий комедийный режиссер! Для того чтоб снимать комедию, надо иметь чувство меры. У тебя его, к сожалению, нет. Давай весь материал на монтажный стол, я тебе склею из него фильм». И Пырьев выкинул пять частей в корзину — все наши усилия, все наши страдания, муки, переживания — всю эту беготню. Вот как был создан «Пес Барбос».

Между тем на волне успеха от этой картины Гайдай вскоре снял ее продолжение — «Самогонщики». Идею этого фильма ему подбросил Ю. Никулин, который в цирке играл подобную интермедию вместе с М. Шуйдиным. И хотя этот фильм в СССР имел меньший успех, чем «Пес Барбос», но его закупили 68 стран, что принесло государству около 70 миллионов рублей. Правда, режиссер с актерами с этого ничего, кроме популярности, так и не поимели.

В 1963 году на экраны страны вышел новый фильм Гайдая «Деловые люди» по рассказам О. Генри. Третья новелла фильма «Вождь краснокожих» стала настоящим шедевром советского комедийного кино. В роли «вождя» снялся начинающий актер Сережа Тихонов, судьба которого, к сожалению, сложилась трагически: в начале 70-х годов он погиб в автокатастрофе.

В прокате 1963 года «Деловые люди» посмотрели 23,1 млн. зрителей. Однако через два года на экранах страны появился очередной фильм Гайдая — «Операция «Ы» и другие приключения Шурика», который мгновенно стал лидером проката — 1-е место, 69,6 млн. зрителей. С этого момента и начался отсчет «золотого десятилетия Гайдая», когда каждый его новый фильм занимал первые строчки в списке самых кассовых картин года.

В последней новелле «Операции «Ы» вновь появилась знаменитая тройка, однако сам Гайдай после съемок внезапно заявил: «Больше отдельных фильмов с этой тройкой снимать не буду.