Первые самолеты вооружались только парой ракет "Сайдуиндер" на законцовках крыла, порт же 20-мм пушки "Вулкан", которую все еще доводили, был заделан, а вместо самой пушки был балласт. Большинство "Старфайтеров" так и использовалось, хотя в принципе подразумевалась и установка двух подкрыльевых контейнеров с пушками "Вулкан" М.61. Первоначально на серийные самолеты ставился двигатель "Дженерал Электрик" J79-GE-3A, а с апреля 1958 г улучшенная модель J79-GE-3B.
Поставки начались с командования ПВО, хотя "Локхид" и не планировала использовать "Старфайтер" в качестве перехватчика. К этому привели проблемы с пушкой, а также требования командования ПВО заполнить паузу между поступлением на вооружение F-102 и F-106. В течении 1958 г F-104 получили четыре эскадрильи перехватчиков: 83-я в Гамильтоне, 337-я в Вестовере, 538-я в Ларсоне и 56-я в Райт Паттерсоне. Освоение F-104 особых трудностей у летчиков не вызывало. Подготовки на тренажерах при этом не требовалось, а учебно-боевые самолеты F-104B поступили несколько позже.
Первый двухместный F-104B поднялся в воздух 16 января 1957 г. Второе место было оборудовало вместо пушки. Еще одним отличием было перемещение носовой стойки, которая теперь убиралась назад, г не вперед, как у F- 104А. Руль направления пол} ил бустер, а площадь стабилизатора была увеличена на 21 %. Первые F-104B поступили в ту же 83-ю эскадрилью перехватчиков в Гамильтоне. Они в основном использовались для переподготовки пилотов и в качестве "вывозных". Всего было выпущено 26 F-104B.
После поступления на вооружение первых "Старфайтеров" фирма "Локхид" обратилась к министерству авиации с просьбой осуществить ряд попыток побить мировые рекорды. В мае было получено соответствующее разрешение. Так как скорости полета ожидались очень высокими, пришлось обратиться в ФАИ, чтобы изменить методику фиксирования результатов полета. Весной 1958 г была одобрена фототеодолитная система измерения скорости и высоты полета. Пробные полеты на динамический потолок показали, что существенно перекрыть рекорд французского "Тридана" фирмы "Сюд авиасьен" не удастся. Однако с помощью ЭВМ удалось рассчитать оптимальную траекторию полета на штурм рекорда высоты. "Атака" рекорда начиналась теперь не с рабочего потолка, где из-за недостатка кислорода горение в форсажной камере прекращалось, а с высоты 13700 м. Рекордный полет на потолок состоялся 7 мая под управлением майора Джексона. Самолет достиг высоты 27811,9 м, а скороподъемность достигала 405 м/с. Весь полет занял 27 минут.
