Идея снять отечественный героико-приключенческий вестерн зародилась в самых высоких кругах — на фоне успеха вышедшего в прокат американского фильма «Великолепная семерка» Никита Сергеевич Хрущев распорядился снять что-то похожее, но в отечественных реалиях. В ЦК комсомола решили экранизировать повесть Павла Бляхина «Красные дьяволята» о Мишке, Дуньке и китайце Ю-ю, которые пробирались в армию Буденного через шайки «махновцев». Повесть уже пережила одну «немую» экранизацию в 1923 году, но теперь из нее было решено сделать блокбастер. Кстати, в первой экранизации вместо китайца был чернокожий акробат из Америки.

«Красные дьяволята», Одесская к/с, 1923, реж. И. Перестиани

Сценарий назывался «Знак четырех» — режиссер Эдмонд Кеосаян вместе со сценаристом фактически переписали первоисточник. Китаец, он же американец в первом фильме, из-за осложнившихся отношений с Китаем и Америкой стал аполитичным цыганом, дописались музыкальные номера, исчез Нестор Махно, но появилось множество новых героев, среди которых был и гимназист Валерка, который символизировал объединение интеллигенции и пролетариата. В ходе работы название сценария поменялось на «Неуловимые из Гуляй-Поля», потом «Мстители из Гуляй-Поля» и в результате получился фильм «Неуловимые мстители».

«Неуловимые мстители», к/с «Мосфильм», 1966, реж. Э. Кеосаян

В ролях подростков Эдмонд Кеосаян планировал снимать учащихся ВГИКа, но они выглядели старше, чем нужно по сюжету. По этой же причине не был утвержден Валерий Носик, который пробовался на роль Валерки. Пробы шли долго, так как к каждому герою было довольно много требований, но в результате были утверждены уже знакомый зрителям по комедии «Добро пожаловать, или Посторонним вход воспрещен» Витя Косых, его друг Миша Метёлкин, спортсменка Валя Курдюкова и цыган из оседлого табора Вася Васильев.

«Неуловимые мстители», к/с «Мосфильм», 1966, реж. Э. Кеосаян

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

«Неуловимые мстители», к/с «Мосфильм», 1966, реж. Э. Кеосаян

На съемочной площадке случались неприятности. Когда Виктор Косых выбежал на дорогу, чтобы спасти детей от мчащейся тачанки, его сбило частью сбруи, и он попал под колеса. Пришлось зашивать рану на лице… На съемках сцены прыжка Яшки со скалы погиб каскадер — ударился головой о неизвестно откуда приплывший лист газетной бумаги, а удар о бумагу на воде равносилен удару об асфальт. Все не знали, что делать, но Васильев сказал, что в дубле снимется сам и выполнил этот трюк… В продолжении фильма рисковал Михаил Метёлкин — когда его Валерка перелетал с лестницей от одного дома к другому, то лестница замерла посередине и опасно наклонилась к проводам под напряжением… Внизу растянули сетку и актер успел спрыгнуть.

«Неуловимые мстители», к/с «Мосфильм», 1966, реж. Э. Кеосаян

С подростками занимались тренеры по борьбе, верховой езде, плаванию, прыжкам в воду, и в результате почти все трюки в фильме они исполняли сами — профессиональные каскадеры заменяли только в самых опасных сценах. Исполнителям главных ролей самим приходилось бывать дублерами и других актеров, и сниматься в массовке. Народа на съемочной площадке не хватало, поэтому иногда Даньке, Ксанке, Яшке и Валерке приходилось переодеваться белогвардейцами и отправляться в погоню за самими собой.