Для установления рекорда скорости была дана неделя (!), чтобы успеть к 17 мая – дню вооруженных сил США. Главной проблемой было удержание самолета в 100-метровом диапазоне высот при подходе к мерной базе и пролета по ней. Кроме того возникла проблема с резким ростом температуры перед компрессором двигателя. Утром 15 мая была осуществлена первая попытка установить мировой рекорд скорости. Во время первого прохода была зафиксирована скорость 2414 км/ч, но из-за поломки и облачности полет пришлось прервать. В следующем полете была показана скорость 2309 км/ч, но ее не удалось зафиксировать наземной аппаратурой; при этом двигатель самолета вышел из строя. Пришлось использовать самолет первых серий, на котором пилот Ирвинг показал в двух проходах скорости 2358,5 и 2161,3 км/ч, что и составило среднюю 2259,94 км/ч. Впервые абсолютные рекорды скорости и высоты полета были установлены на одном самолете! Штурм рекордов продолжался – до декабря 1958 г было установлено еще семь рекордов скороподъемности.
В октябре 1958 г во время очередного обострения "китайско-китайских" отношений 12 F-104A из 82-й эскадрильи были в разобранном виде доставлены на Тайвань. Сами они не могли туда перелететь из-за ограниченной дальности полета. В результате несколько машин получили штанги системы дозаправки топливом, но это так и осталось экспериментом. Принять участие в боях "Старфайтерам" тогда так и не удалось.
К 1959 г проявились технические дефекты самолета, особенно с двигателем: неравномерность работы, выбросы пламени из компрессора, срыв горения в форсажной камере. Произошло несколько катастроф, и полеты были прекращены на некоторое время. Все самолеты были переоснащены на двигатели J79-GE-3B. ВВС тем временем отклонили заказ на 18 тактических разведчиков RF-104, а также на тренировочные TF-104. В начале 1960 г ВВС США решили ограничиться покупкой только 153 F-104A, одновременно "Старфайтеры" стали передаваться в ВВС национальной гвардии. Первой получила F-104A 157-я эскадрилья перехватчиков на базе Макзнтир, потом 151-я в Тизоне, 197-я в Скаухарборе. С возникновением берлинского кризиса их перебросили в Европу, 157-ю – в Испанию, а 151 -ю и 197-ю – в Западную Германию на базу в Рамстейне. Лишь в конце 1962 г эскадрильи национальной гвардии вернулись в США, но с октября разразился новый кризис – кубинский.
К этому времени в штабе ВВС уже оформилось мнение о F-104, как об идеальной "пожарной команде". Простота самолета и его обслуживания (все наземное оборудование на 21 прицепе небольшого размера легко перебрасывалось по воздуху), отличные летные данные позволяли быстро перемещать его для прикрытия с воздуха важных объектов. Не удивительно, что в 1963 г F-104 забрали из ВВС национальной гвардии и вооружили ими 319-ю и 331-ю эскадрильи ПВО, находившиеся во Флориде. 319-я эскадрилья оставалась во Флориде с F-104A до декабря 1969 г, а 331-я во время вторжения американцев в Доминиканскую республику в мае 1965 г была переброшена в Пуэрто-Рико. Именно здесь во время кубинского кризиса произошло первое столкновение F-104A со своим основным "заочным" противником – МиГ-21. Американцы активно использовали свои самолеты для демонстрации силы, совершая полеты над Кубой на малой высоте. Среди советских частей, прибывших на Кубу был гвардейский истребительный полк с Кубинки, только что перевооруженный на МиГ-21 Ф. Открывать огонь по одиночным американским самолетам запрещалось, но у советских летчиков родилась идея принудить к посадке один из F-104. В результате нескольких таких попыток, конечно, ничего не получилось – "прижать" сверхзвуковой самолет дело весьма сложное – но "взаимное маневрирование" показало полное превосходство МиГ-21 над "Старфайтером".
F-104A недолго пробыл на вооружении ВВС, но неожиданно попал во флот! ВМС также мечтали попасть в клуб "Двух Махов", но их собственный истребитель "Чане Воут" F8U "Крусейдер" еще не был готов. В результате в 1959 г флот взял внаем три "Старфайтера": YF-104A (№55-2956) и два F-104A (№№56-0740 и 0757). Они комплектовались экипажами из 83-й эскадрильи и испытывались на базе флота Чина-лейк в 1960-61 гг. Причем оба F-104A разбились. Этот каприз судьбы интересен тем, что F-104 носил полную маркировку флота.