Режиссёр фильма Марлена Хуциев был ещё начинающим автором, но уже зарекомендовал себя как крепкий мастер, сняв знаковую романтическую комедию «Весна на Заречной улице». На съемках «Весны» режиссёр хорошо сработался с молодым оператором Петром Тодоровским и пригласил его на фильм «Два Федора» в качестве главного оператора. В перспективе Тодоровский сам проявит себя как режиссёр и снимет такие фильмы, как «Военно-полевой роман», «Интердевочка», «По главной улице с оркестром» и «Риорита».
Роль Фёдора-большого стала первой главной в кинематографической судьбе Василия Шукшина. Фильм все еще находился на стадии проработки сценария, на Одесской киностудии, там же на практике находился студент режиссерского факультета ВГИКа Василий Шукшин. Режиссер Марлена Хуциев периодически сталкивался с Шукшиным в аллее киностудии. Хуциев сразу увидел в Шукшине своего героя, но не предлагал роль из профессиональной вежливости, Шукшин проходил пробы на другой фильм. Когда пробы закончились для Шукшина неудачно, Хуциев предложил ему ознакомиться со сценарием.
После того, как Шукшин согласился на роль в фильме «Два Федора», на проекте, где он неудачно проходил пробы, произошли пертурбации в актерском составе, и Шукшина пригласили на главную роль. Актер объяснил, что уже принял другое предложение, но его обманули, сказав, будто фильм Хуциева забраковали и он не будет запущен в производство. Сценарий фильма утверждался комитетом в Киеве. Правки были небольшими, и Хуциев решил доработать его на месте сразу в режиссёрском сценарии. Приехав в Киев на съемки, Шукшин зашел к Хуциеву поздороваться и узнал об обмане. Шукшин со скандалом ушел с текущего проекта, и влился в группу Хуциева.
Мальчишку сыгравшего Федора-маленького зовут Коля Чурсин. В жизни Коля был закоренелым двоечником и хулиганом, никогда не занимавшимся самодеятельностью. Ассистенты режиссёра заметили его в харьковском доме пионеров, где парень оказался случайно. Мальчишка подкупил режиссёра природным артистизмом и своей непосредственностью.
Во время съемок мальчик подружился с Шукшиным и после окончания работы над фильмом они продолжили общаться. Коля не принимал важных решений, не посоветовавшись со своим старшим другом. Во время съемок сцены на станции Коля едва не попал под колеса поезда, Шукшин отчаянно бросился на помощь и спас мальчика, хотя сам получил ранение.
Накануне премьеры фильма в столичном Доме кино Шукшин напился и участвовал в потасовке в общественном месте, в результате чего его задержала милиция и поместила под арест. Отсутствие актера, исполнившего главную роль, на премьере фильма было неприятным инцидентом, и Хуциев отправился спасать актера. Режиссеру удалось освободить Шукшина только в обмен на пригласительные на премьеру для начальника отделения и его семьи.
Фильм вышел зимой 1959 года. Трогательная история о дружбе фронтовика и мальчишки-беспризорника была тепло принята зрителями, и картина вошла в золотой фонд советского кино.
