Фильм снят по мотивам книги Джона Б. Холуэя Красные хвосты, чёрные крылья: Чёрные мужчины BBC Америки.
Идея постановки фильма об афроамериканских пилотах, известных под названием Лётчики Таскиги (The Tuskegee Airmen), появилась у Джорджа Лукаса ещё в 1988 году. На то время предположительной датой релиза был 1992 год, сценарием должен был заняться Кевин Салливан, а режиссёром стать Томас Картер.
После того как от работы с проектом отказались все крупные киностудии Голливуда, Джорджу Лукасу пришлось практически полностью финансировать 58-миллионный бюджет картины плюс выделить дополнительно 35 миллионов долларов на подготовку релиза и рекламную кампанию.
Летом 2008 года Джордж Лукас в частной беседе предлагал место режиссёра Сэмюэлу Л. Джексону. Рабочий сценарий будущего фильма понравился тому, однако отказаться на полтора года от своей актёрской карьеры Сэмюэл Джексон был не готов.
Во время съёмок в Чехии актёры прошли две с половиной недели тренировочного лагеря. Условия в нём были максимально приближены к тем, что имели в период подготовки лётчики программы Таскиги в период Второй мировой войны.
В марте 2010 года при пересъёмке отдельных сцен режиссёр Энтони Хемингуэй был занят работой на телевидении над сериалом Тримей. В его отсутствие обязанности режиссёра пришлось взять на себя Джорджу Лукасу.
За семнадцать лет до выхода Красных хвостов Кьюба Гудинг мл. сыграл одну из главных ролей в также посвящённом афроамериканским лётчикам телевизионном фильме канала HBO Пилоты из Таскиги (1995).
Терренс Ховард ранее играл лётчика Таскиги в фильме Война Харта (2002).
До стартовавшей в 1941 году экспериментальной программы Таскиги афроамериканцам не разрешалось служить в военной авиации. Всего в рамках этой программы с 1941 по 1946 год было подготовлено 996 афроамериканских пилотов. Окончательное решение об отмене расовой сегрегации в американской армии было принято президентом Трумэном только в 1948 году.
За пару лет до начала непосредственной работы над фильмом несколько лётчиков-ветеранов получили приглашение на знаменитое ранчо Джорджа Лукаса в Калифорнии. Их рассказы и воспоминания были использованы при дальнейшей разработке проекта.
Студия Lucasfilm получила доступ к хранящимся в музеях и архивах полётным журналам пилотов программы Таскиги.