Строевые летчики ожидали найти в «Старфайтере» нечто лучшее, чем F-100, но их надежды не оправдались. Новый самолет уступал «Супер Сейбру» по дальности полета на 900 км, по полезной нагрузке на 1300 кг и проигрывал в маневренности. Особенно ярко выглядело отставание в вооружении. Главная изюминка проекта — пушка М61 оказалась ненадежной и опасной в эксплуатации. Сильные вибрации, частые взрывы боеприпасов в казеннике и теоретическая возможность догнать собственные снаряды при стрельбе на большой скорости привели к тому, что летчики просто боялись нажимать боевую кнопку. 1 ноября 1957 г. командование ВВС запретило стрельбу из пушки, потребовало от фирмы снять М61 со всех F-104A и больше не устанавливать ее на строящиеся самолеты. Таким образом, единственным вооружением у «Старфайтера» оставались две управляемые ракеты «Сайдвиндер». Забегая вперед, следует заметить, что боевые F-104A не имели встроенного вооружения до 1964 г., пока не появилась более надежная пушка М61А1.
В конце концов представители Тактического авиационного командования ВВС (Tactical Air Command — ТАС) заявили, что не будут включать «Старфайтеры» в состав боевых частей. Это был сильнейший удар по престижу «Локхида» и лично по Джонсону.
Положение фирмы спасли задержки поставок истребителя- перехватчика F-106 Delta Dart фирмы Convair. Обеспокоенное этим фактом Командование противовоздушной обороны решило взять «забракованный» F-104A на вооружение своих частей, пока «Конвэр» не решит возникшие проблемы. Одной из основных причин такого решения стали высокие скорость и скороподъемность «Старфайтера», причем последняя намного превосходила аналогичный показатель любого другого американского перехватчика того времени.
Первая партия F-104A поступила на вооружение 83-й эскадрильи перехватчиков (FIS) на авиабазе Хамилтон в Калифорнии. 20 февраля 1958 г. ее самолеты начали нести боевое дежурство. Затем последовали: 56-я FIS на базе Райт Паттерсон в Огайо, 337-я FIS на базе Вестовер в Массачусетсе и 538-я FIS на базе Ларсон в штате Вашингтон. Правда, F-104A не были всепогодными и не могли взаимодействовать с автоматизированной системой SAGE, но на это временно закрыли глаза.
На самолетах стояли двигатели J79-GE-3 или -3А. По результатам эксплуатации все они оказались весьма ненадежными, и по их вине произошло несколько летных происшествий. Наиболее опасными были отказы системы регулирования сопла и неисправности системы подачи масла.
Сопло при включении форсажа раскрывалось, а после выключения часто заклинивало и оставалось в открытом положении, что приводило к резкому падению тяги до уровня «малый газ». Такой тяги просто не хватало для горизонтального полета, и летчикам приходилось катапультироваться.
В апреле 1958 г. командование ВВС прекратило полеты F-104A до замены всех двигателей на новую модификацию J79-GE-3B (тяга на форсаже 6719 кгс). Через два месяца «Старфайтеры» стали постепенно возвращаться в строй, но ситуация с уровнем аварийности изменилась мало. F-104 продолжал лидировать по количеству отказов среди других самолетов «сотой серии».
В июне 1958 г. один F-104A был облетан британским летчиком-испытателем Роландом Бьюмонтом (Roland Beaumont) из фирмы English Electric. После полета он рассказал, что практически на всех режимах ощущались короткопериодические колебания с низкой амплитудой, причем система демпфирования их не парировала. Управление по крену требовало от летчика больших усилий. Маневренность также оставляла желать лучшего. Бьюмонт даже попал в плоский штопор, но достаточный запас высоты позволил ему выйти из этого опасного режима. Flo особенно угрожающими он счел взлет и посадку, которые требовали от летчика большой точности и координации при работе с органами управления двигателем и самолетом. По его мнению, эксплуатация F-104 в строевых частях могла привести к большому количеству аварий и катастроф. Этот вывод точно соответствовал реальному положению вещей.
Хотя статистику аварийности секретили, но некоторые факты утаить от общественности было просто невозможно. В полетах на F-104A погиб 21 пилот ВВС США. Среди них оказался и известный американский летчик Айвин Кинчилоу (Iven С. Kincheloe). Он прославился еще в Корее, сбив 5 и повредив шесть МиГ-15. После войны Кинчилоу служил на авиабазе Эдвардс и принимал участие в программе Х-2. 7 сентября 1956 г. он поднялся на высоту 38405 м, за что пресса назвала его «первым американским астронавтом». Айвин погиб 26 июля 1958 г. из-за отказа двигателя F-104A на высоте 600 м. Сначала он пытался спасти самолет, но тот слишком стремительно снижался, и Кинчилоу решил покинуть машину. Он начал переворачивать истребитель, т.к. для безопасного катапультирования вниз высоты уже не хватало. Видя, что закончить этот жизненно важный маневр он уже не успеет, Айвин катапультировался в сторону. Парашют не успел раскрыться, и Кинчилоу разбился. Этот случай заставил конструкторов отказаться от катапультирования вниз и поставить на самолеты более совершенные кресла типа С-2, выстреливавшие пилота вверх.
