Леонид Гайдай, Сняв "Операцию "Ы", считал, что этот фильм опустошил его как режиссера, что Шурик уже себя исчерпал, да и троица тоже. Поэтому ему хотелось снимать иное кино, тоже комедию, но уже с другими персонажами. Но руководство Мосфильма, видя, какой триумф обрушился на "Операцию "Ы", чуть ли не в приказном порядке заставило Гайдая взяться за продолжение фильма. 15 июня 1965 года заявка сценаристов на новую комедию поступила в творческое объединение Луч при киностудии Мосфильм и была принята. Будущий сценарий носил название "Шурик в горах"
Сценарий состоял из двух новелл. В первой "Кавказская пленница" речь шла о том, как красивая девушка Нина приехала на каникулы к своим родственникам на Кавказ, но была похищена местным сластолюбивым князьком Ахоховым. Но Шурик вызволяет девушку из рук похитителя.
Во второй новелле "Снежный человек и другие" сюжет был таков: научная экспедиция под руководством видного ученого (роль писалась специально под Михаила Пуговкина, несмотря на то, что худрук Луча Пырьев был против этой кандидатуры) ищет в горах снежного человека. Ей удается выйти на его след, но поймать не получается. Но группа даже не догадывается, что за снежного человека себя выдает троица в лице Труса, Балбеса и Бывалого. После того как провалилась их затея с похищением Нины, они сбежали в горы и стали выдавать себя за "снежного человека", чтобы сбить со следа милицию. Однако Шурик и Нина разоблачают авантюристов
Впоследствии от новеллы о "йети" съемочная группа отказалась, расширив первую часть до хронометража полноценного фильма
На роль Нины долгое время не могли найти подходящую актрису — пришлось провести более 500 фотопроб, и в итоге выбор остановили на Наталье Варлей. Ввиду того, что до начала карьеры актрисы она работала в цирке канатоходкой, ей хорошо давались трюковые сцены. Однако в её случае проблему составляли игровые сцены из-за отсутствия актёрских навыков.
В случае Саахова возникли расхождения во взглядах на образ персонажа между Леонидом Гайдаем и исполнявшим роль Саахова Владимиром Этушем. Если последний из них воспринимал своего персонажа всегда серьёзным человеком, в частности, не понимающим, как могли отвергнуть его ухаживания и облить вином, то Гайдай хотел сделать гротескный образ.
В процессе разработки сценарий многократно изменялся цензурой. Так, пришлось видоизменить фразу Труса «Да здравствует советский суд, самый гуманный суд в мире!» на «Да здравствует наш суд, самый гуманный суд в мире!», так как изначальный вариант посчитали издевательством над советским судом. Также пришлось вырезать заставку, в которой Бывалый пишет на заборе «Х», Балбес приписывает «У», а Трус, увидев милиционера, дописывает «дожественный фильм».
И хотя пробный показ ещё не утверждённого Госкино фильма имел огромный успех, тем не менее выпускать картину в прокат не решались. Однако фильм посмотрел Леонид Брежнев и поблагодарил за хорошую кинокомедию, что решило судьбу фильма. В итоге в прокате 1967 года фильм занял первое место, и за год его посмотрело 76,54 млн зрителей.