Во время посещения Ленинградского музея уголовного розыска писатель Израиль Меттер обратил внимание на чучело овчарки. Литератора заинтересовал столь необычный экспонат, он решил разузнать за какие заслуги он выставлен для обзора.
Вскоре удалось выяснить биографию необычного пса. Его звали Султан и он поучаствовал в задержании свыше тысячи преступников, смог найти похищенного имущества на сумму примерно 3 000 000 рублей.
Трудовая деятельность Султана связана с блокадным Ленинградом, за время своей работы пес был дважды ранен. Когда наступило время, что Султан уже не мог выполнять служебные обязанности, его забрал доживать век проводник майор Петр Бушмин. Меттер смог встретиться с майором, который рассказал много интересных моментов из жизни Султана, а также о кинологической службе вообще. Рассказы были столь интересны и глубоко раскрывали психологию поведения друзей человека, что писатель решил попробовать написать повесть о служебно-разыскной собаке. Так появилась повесть "Мухтар", опубликованная в 1960 году в литературном журнале "Новый мир" (в своем произведении автор сменил кличку собаке). Повесть оказалась довольно удачной и ее решили экранизировать, писать сценарий будущего фильма поручили самому Меттеру.
Еще до начала съемок было понятно - главную роль должны сыграть несколько псов - вначале фильма Мухтару должно быть всего полтора года, а к концу ему должно было исполниться около 10 лет. Да и животные плохо переносят съемки, поэтому запасные собаки должны были быть в любом случае. Двух псов среднего возраста Урала и Байкала выделило Министерство внутренних дел, они к тому моменту были уже опытными служебно-розыскными собаками, а третьего приобрел "Мосфильм". Юный пес был озорным и совершенно непослушным, дрессировке поддавался плохо, поэтому в кадре появлялся только когда требовалось подчеркнуть молодость животного.
На предложение режиссера Сергея Туманова сыграть главную роль, Юрий Никулин поначалу ответил категорическим отказом. Дело было в том, что в двух последних своих фильмах актер играл жуликов и он не представлял как после этого можно играть милиционера. Туманова подобные заявления совершенно не испугали - он указал Никулину на весьма существенный козырь для принятия роли. Мужчина выступал в цирке и прекрасно умел обходиться с животными, да и предоставленные внутренними органами собаки тоже умели взаимодействовать с человеком. Несколько недель до съемок комик по утрам выгуливал своих новых подопечных, кормил изх, а затем отправлялся на работу в цирк. Вечером кормление и прогулка повторялась.
Уже во время съемок начального эпизода возникли сложности - Глазычев с Мухтаром шли по следу рецидивиста в сильную метель. Метель создавали мощные ветродуи, от дикого воя которых собаки в ужасе разбегались. Нужен был пес, которого этот шум не испугает. И тут мосфильмовцы вспомнили о пришедшем ранее письме, в котором один инженер предлагал свой вариант "Мухтара", а еще рассказывал о своем псе Дейке, как будто идеально подходящем на роль Мухтара. Инженера срочно пригласили вместе с собакой - результаты проб превзошли все ожидания. Дейк действительно оказался очень умным и сообразительным псом, он прекрасно выполнял все команды и ничего не боялся. В результате большую часть съемок прошел именно новичок.
Льву Дурову игравшему рецидивиста не повезло - момент задержания прошел слишком реалистично. Мухтара в тот момент играл Байкал, а он воспринял задержание всерьез. За несколько секунд, пока его не оттащили, пес порвал верхнюю одежду и оставил актеру на ноге шрам на всю жизнь.