Вступив в войну в Корее, США направили на Дальний Восток соединения бомбардировщиков B-29, но вскоре выяснилось, что существующие истребители США не могли сопровождать эти бомбардировщики. Хотя F-84 обладал необходимой дальностью полета, он не мог противостоять советским истребителям МиГ-15, а хорошо показавший себя в боях истребитель F-86 имел недостаточную дальность полета. Стратегическая авиация США нуждались в новом истребителе, сочетающим в себе лучшие качества обоих машин.

Победу в конкурсе одержала компания McDonnell, предложившая проект, в основе которого лежал истребитель XF-88. Новый самолет получил обозначение F-101 Voodoo. Он сохранил конфигурацию самолета XF-88, но был значительно больше по размерам. На истребитель установили осевые турбореактивные двигатели Pratt & Whitney J-57, возросший расход воздуха потребовал увеличить воздухозаборники. Для размещения большого запаса топлива увеличили размеры фюзеляжа, соответственно возрасла площадь крыла. Цельноповоротный хвостовой стабилизатор установили почти на самом верху киля. В конструкции самолета широко применялся титан. Вооружение самолета состояло из четырех 20-мм пушек М-39Е. Под фюзеляжем имелось три узла подвески для 1800кг боевой нагрузки, в том числе одной ядерной бомбы.

Так как схема самолета была отработана еще на XF-88, то прототипа F-101 не строили, а испытания проводили на первом серийном образце. Первый полет был выполнен 29 сентября 1954 года. В результате испытаний выявилась статическая неустойчивость и продольное раскачивание самолета. Самой трудной проблемой оказался помпаж двигателя J-57. В связи с задержками на устранение выявленных недостатков, темп выпуска серийных самолетов был невысоким.

Первый F-101A был принят на вооружение в мае 1957 года. Но к этому времени было решено, что бомбардировщики B-47 и B-52 способны выполнять свои задачи без истребительного прикрытия и Voodoo были переданы тактической авиации. В октябре 1957 года начался выпуск модификации F-101C с усиленной конструкцией.

Хотя Voodoo был самым современным самолетом, он не совсем подходил для тактического использования. В 1958 году истребители F-101 были переданы в состав ВВС США в Европе. В середине шестидесятых их сменили на F-4 Phantom.

Около шестидесяти самолетов F-101 были модифицированы в тактические разведчики RF-101 специально для ВВС национальной гвардии. Вместо встроенных пушек на самолет установили фотооборудование и новый носовой обтекатель с окнами для фотокамер. Разведчики оставались на вооружении до 1972 года.

Последней крупной серией самолета стал двухместный F-101B, предназначенный для решения широкого круга задач, включая ведение перехвата и применение управляемых и неуправляемых ракет. Перехватчик F-101B хорошо подходил для службы в удаленных районах США. Первый полет нового варианта состоялся 27 марта 1957 года. В процессе испытаний были выявлены многочисленные недостатки, наиболее серьезным их которых оказалась устаревшая система управления огнем Hughes MG-13. Тем не менее в январе 1959 года F-101B начал поступать на вооружение ПВО.

Первоначально перехватчик вооружался только четырьмя ракетами "воздух-воздух" AIM-4 Falcon, позже он получил возможность нести ядерные неуправляемые ракеты AIR-2 Genie. В середине шестидесятых годов была проведена доработка системы управления огнем для перехвата низколетящих целей, установлен инфракрасный локатор и доработан автопилот. Перехватчики F-101B сохранялись в боевых эскадрильях ПВО до 1968 года, а в национальной гвардии самолеты оставались до 1983 года.

Выпуск истребителей Voodoo продолжался до марта 1961 года, всего было построено 807 машин. Обозначение F-101F (TF-101B) получили самолеты с двойным управлением. Хотя этот вариант и обладал всеми возможностями перехватчика, он в основном использовался для тренировок и повышенной летной подготовки экипажей. ВВС Канады было передано 112 самолетов CF-101B и 20 учебных CF-101F, которые эксплуатировались до 1985 года.