Взяв за основу идею Бляхина, авторы сценария, по сути, переписали сюжет, введя новых героев и персонажей. В фильме Перестиани юных героев играли цирковые артисты П. Есинковский, С. Жозефи и Кадор Бен-Салим. Им, как говорится, сам бог велел без дублеров выполнять рискованные трюки. Но практически то же самое пришлось делать и четверке героев нового фильма.
Вите Косых, который в 13 лет стал известным актером благодаря роли Кости Ивочкина в фильме «Добро пожаловать, или Посторонним вход воспрещен» (1964), и Васе Васильеву, приехавшему на пробы из города Вязники Владимирской области и выбранному из 8000 (!) претендентов, было в то время около 16. А Мише Метелкину еще не исполнилось 14. Он и по росту был меньше всех. И режиссер сказал ему: «Ешь морковку. Подрастешь, тогда и приходи». Подростку так хотелось участвовать в этом фильме, что он всерьез воспринял совет режиссера и в огромных количествах ел тертую морковь со сметаной. И за несколько месяцев до начала съемок действительно подрос. На целых 7 сантиметров! Кстати, название фильму придумали именно Миша Метелкин и Витя Косых.
По-разному сложились судьбы у четверки неуловимых.
Только Виктор Иванович Косых (р. 27.01.1950) стал профессиональным артистом и продолжает сниматься: «С тобой и без тебя» (1973), «Фронт за линией фронта» (1977), «Трактир на Пятницкой» (1977), «Пограничный пес Алый» (1979), «Сказка, рассказанная ночью» (1981), «Тревожное воскресенье» (1993), «Утро обреченного прииска» (1985), «Холодное лето 53-го» (1988), «Маэстро вор» (1994) «Звезда эпохи» (2005), «Почтальон» (2008) и др.
Михаил Метелкин после трилогии о мстителях снялся еще в нескольких картинах, но посвятил себя режиссуре художественного и документального кино. Эдмонду Кеосаяну во время съемок картины пришлось даже срочно пристраивать Михаила, которому грозил призыв в армию, на экономический факультет ВГИКа.
Роль цыганенка Яшки у Василия Васильева — единственная экранная работа. Какое-то он время играл в театре «Ромэн», занимался концертной деятельностью. Потом занялся бизнесом и живет с семьей в Твери.
Валя Курдюкова на картину попала случайно: в спортивную школу, где она занималась в секции спортивной гимнастики, пришли ассистенты, чтобы посмотреть девочек на роль Ксении. И остановились на Курдюковой. Несмотря на оглушительный успех фильма и последовавшие за ним два продолжения, Валентина не захотела связать свою жизнь с кино: окончила цирковое училище. Потом какое-то время работала буфетчицей в Моссовете. Вышла замуж за Анатолия Калмыкова. Во второй раз она вышла замуж за Бориса Сандуленко — цыгана, эстрадного певца. У них двое детей.
В фильме снимались как известные актеры, так и те, кого потом узнавали именно после «Неуловимых…». Савелий Крамаров, уже многое успевший сделать в кино до роли бандита Игната, вошел в народную память и фольклор своей фразой: «А вдоль дороги мертвые с косами стоят… И тишина!»
Ефим Захарович Копелян (12.04.1912—06.03.1975) вначале пробовался на роль Лютого. Но режиссер посчитал, что он несколько староват для нее, и взял его на роль батьки Бурнаша. Копелян, сыгравший не так много ролей в кино («Опасные гастроли» (1967), «Интервенция» (1968), «Ошибка резидента» (1968), «Преступление и наказание» (1969), «Судьба резидента» (1970), «Чайка» (1970), «Вечный зов», (1973, сериал) и др.), активно занимался дубляжом, а его закадровый текст в «Семнадцати мгновениях весны» считается одной из удач этого культового фильма.
Увидев красивого и фактурного Владимира Трещалова, которого пригласили в массовку, Кеосаян сразу утвердил его на роль Сидора Лютого. Трещалов прекрасно держался в седле и сам выполнял все трюки, в том числе, имитируя смерть, на скаку повисал на стремени. Он серьезно повредил ногу, ходил какое-то время с палочкой. Правда, режиссер потом не раз пожалел о своем решении. Из-за взрывного характера артист постоянно наживал себе неприятности и врагов. Вдрызг разругавшись с режиссером, Трещалов подписал своему герою смертный приговор: Лютого убивают в первом же фильме, хотя его участие планировалось во всех последующих продолжениях. Его даже озвучивал уже другой артист — Евгений Вестник.
Артист Москонцерта Борис Сичкин, узнав, что в фильме фигурирует реально существовавшая личность — куплетист Буба Касторский, сам пришел к Кеосаяну и убедил его дать ему эту роль. С той поры фраза «Я одессит. Я из Одессы. Здрасте!» стала визитной карточкой артиста, сделавшегося в одночасье необычайно популярным в свои 44 года.
Блеснула комедийным талантом в небольшом эпизоде и Инна Чурикова, сыгравшая Белокурую Жази, сама исполнившая сладострастный «жестокий романс».