Пока компания вносила изменения в свой проект, изменились и взгляды ВВС США. Первоначально F-101 рассматривался в качестве временного решения, "ступеньки" к новому дальнему истребителю. Однако, ко времени окончательного выбора, ВВС переменили свое решение, посчитав, что, так называемый, "окончательный" дальний истребитель вполне можно получить путем последовательной модернизации "Вуду". В частности это означало, что на первых F-101 должна быть предусмотрена установка не только уже существующего оборудования, но и перспективных авионики и двигателей так, чтобы по мере поступления новой, более совершенной авионики уже выпущенные самолеты можно было бы соответствующим образом модернизировать.
Одновременно было решено использовать для запуска "Вуду" в производство принцип "сэндвича" (или слоенного пирога). Чтобы ускорить принятие самолета на вооружение, предусматривалось почти сразу после минимальных необходимых испытаний выпустить небольшую серию, одновременно готовя полномасштабное, серийное производство варианта, в который можно было бы быстро внести изменения, продиктованные выявленными недостатками. Таким путем надеялись избежать конструкторских ошибок на возможно ранней стадии и уменьшить стоимость программы устранения возможных недостатков.
15 января 1952 года "МакДоннелл" получила предварительный контракт от ВВС. Производство в Сент-Луисе началось почти немедленно. Вслед за этим, 11 июня был подписан "нормальный" заказ на определенную сумму. 21 июля состоялась макетная комиссия, ставшая первой из целой серии проведенных в течение нескольких следующих лет. Так комиссия 17-18 марта 1953 года исследовала возможность использования самолета как носителя тактического ядерного оружия.
Так как основой для F-101 послужил XF-88, то опытного самолета в привычном смысле слова не было. Первый F-101 (53-2418) стал одним из 29 самолетов, заказанным в 53-м финансовом году. Этот самолет был сдан ВВС согласно плана в августе 1954 года. Самолет был доставлен на авиабазу Эдвардс, откуда он и совершил свой первый полет 29 сентября. Пилот Боб Литтл в этом полете достиг скорости М=1,07. Соглашение о перемирии в Корее тут же отозвалось на программе "Вуду" – ВВС подошли к запуску в серию нового самолета более осторожно. Это отразилось в мае 1954 года на решении задержать финансирование по F-101A до выполнения испытательных полетов "Категории"-П, что привело к отсрочке серийного производства, хотя уже в конце октября 1954 года "замораживание" было снято за несколько месяцев до начала испытаний "Категории"-Н.
К концу 1954 года еще три F-101A поступили на авиабазу Эдвардс. Они предназначались для испытаний по "Категории-I". Именно на этой стадии стало ясно, что имеется целый ряд проблем. В результате испытаний по "Категории-Н" были выявлены недостатки, некоторые из которых оказалось трудно устранить. Наиболее серьезными недостатками были продольное раскачивание и статическая неустойчивость. В отчете о недостатках упоминались даже примеры того, что самолет просто беспорядочно кувыркался. В результате был установлен активный демпфер на систему управления по тангажу. Таким образом, к 1956 году удалось устранить большинство недостатков. Такой же трудноразрешимой проблемой стал помпаж двигателя J-57. Эта и другие проблемы привели к еще одной задержке производства в мае 1956 года, хотя и на короткое время. Тем не менее темп выпуска F-101 был невысоким в течение почти всего 1956 года, пока ВВС проводили пересмотр проекта. Так продолжалось до ноября, когда последние ограничения были сняты. Но даже после этого, решение ВВС США продолжить работу над F-101 было обусловлено значительными изменениями в программе. Чтобы понять, что же произошло, следует вернуться в март 1952 года.
В это время "МакДоннелл" выдвинула официальный запрос ВВС, в котором предлагалось, чтобы первые 33 "Вуду" имели ограничение по перегрузке 6,33g, после чего следовало переключиться на вариант, способный выдержать 7,33g. Но до осени 1955 года программа испытаний и производства первоначальной модели F-101A велись неритмично, и не было никакой возможности обеспечить необходимую доработку конструкции, начиная ранее 116-го самолета. В результате пришлось рассматривать различные варианты модернизации, включая полную переделку первых 115 машин. Но в конце концов, в июне 1956 года ВВС решили принять первую партию, как она есть. При этом обозначение "А" осталось за первой серией, а самолеты рассчитанные на 7,33g получили обозначение F-101C. Затем, в декабре 1956 года произошло очередное, упомянутое выше изменение программы, обусловившие, что последние 96 из 220 первоначально заказанных F-101A следовало закончить в варианте RF-101 С.