Le F-104A fut utilisé pendant quelques temps en tant qu'intercepteur par l'Air Defense Command/Aerospace Defense Command de l'USAF, bien que l'armement et le rayon d'action du Starfighter ne soit guère adapté à cette mission. Le 20 février 1958, le 83rd Fighter Interceptor Squadron de Hamilton AFB fut la première unité à être opérationnelle sur F-104A. Après une série d'accidents dus aux moteurs de ses F-104A, l'unité fut interdite de vol après seulement trois mois d'activité. Les vols ne reprirent qu'une fois que les réacteurs aient été remplacés par des J79-3B, et trois nouvelles unités de l'ADC furent transformées sur F-104A. En même temps, l'USAF réduit sa commande initiale de 722 Starfighter à 155. Les Starfighter de l'ADC furent retirés des unités d'active après un an de service et transférés vers des unités de l'Air National Guard. Il est néanmoins important de se rappeler que le F-104 avait été conçu comme une solution d'attente avant la livraison des F-106 Delta Dart.
La version suivante, F-104C, entra en service avec le Tactical Air Command en tant que chasseur-bombardier multirôle. Le 479th Tactical Fighter Wing de George Air Force Base fut la première unité à voler sur cet appareil à partir de septembre 1958. Bien qu'il ne soit guère adapté au théâtre d'opérations, le F-104 fut utilisé pour quelques missions pendant la Guerre du Vietnam. En 1967, les Starfighter du TAC sont transférés à l'Air National Guard.
La participation du Starfighter commença lors de l'Opération Rolling Thunder en 1965. Bien qu'ils aient été utilisés dans le cadre de missions de supériorité aérienne et de support aérien, les F-104 ne connurent que peu d'engagements avec des appareils ennemis et aucune victoire mais eurent néanmoins un important rôle de dissuasion contre les MiG.
Le premier des deux déploiements de Starfighter au Vietnam eut lieu entre avril 1965 et novembre 1965 avec un total de 2 937 sorties de combat. Pendant ce déploiement, deux F-104 furent descendus par des tirs venant du sol, un autre abattu par un Shenyang J-6 (version chinoise du MiG-19) alors qu'il passait au-dessus de la frontière et deux autres enfin perdus suite à une collision en plein vol lors d'un engagement au combat. Le 476th Tactical Fighter Squadron fut déployé d'avril 1965 à juillet 1965, perdant un Starfighter. Le 436th TFS quant à lui perdit quatre appareils lors de son déploiement de juillet 1965 à octobre 1965.
Les Starfighter connurent leur deuxième déploiement au Vietnam quand le 435th TFS y séjourna de juin 1966 à juillet 1967 accomplissant 2 269 sorties de combat. Neuf autres F-104 furent perdus : deux victimes des tirs venant du sol, trois descendus par des missiles sol-air et quatre suite à des incidents mécaniques (problèmes de réacteurs).
Alors qu'ils étaient remplacés par des F-4 Phantom II en juillet 1967, un total de quatorze F-104 avait été perdu au Vietnam.
Les F-104 en service au Vietnam furent modernisés avec des récepteurs radar d'alerte APR-25/26, l'un d'entre eux étant toujours exposé à l'Air Zoo de Kalamazoo (Michigan).
L'USAF ne fut pas très satisfaite du Starfighter et n'en commanda que 296 exemplaires monoplaces et biplace toutes versions confondues. A cette époque, la doctrine de l'USAF ne laissait que peu de place à la supériorité aérienne (les « vraies » missions de chasse), et le Starfighter ne sembla pas répondre aux besoins en termes d'intercepteur ou de chasseur-bombardier tactique, car il manquait à la fois de la capacité d'emport et de capacité de survie des autres chasseurs de l'époque en service auprès de l'USAF.
Son utilisation dans l'USAF déclina dès la fin de 1965, les derniers Starfighter en service actif quittant l'USAF en 1969. Le F-104 resta néanmoins dans les rangs de la Garde nationale de Porto Rico jusqu'en 1975.
Les derniers Starfighter à voler sous les couleurs américaines furent les F-104G et TF-104G de la Luftwaffe basés à Luke Air Force Base (Arizona) pour l'entraînement des pilotes allemands. Malgré leurs cocardes de l'USAF, ces Starfighter (dont certains construits en Allemagne) appartenaient en fait à l'Allemagne. Ils continuèrent à voler jusqu'en 1983.
Le 13 janvier 1967, quatre F-104G de la Force aérienne de la République de Chine engagent le combat contre une formation de 12 MiG-19 de la Force aérienne chinoise au-dessus de l'ile de Kinmen. Un MiG-19 fut abattu de même qu'un F-104.
Au petit matin du 6 septembre 1965, le Flight Lieutenant pakistanais Aftab Alam Khan marqua le début des combats aériens pendant la guerre entre l'Inde et le Pakistan de 1965 en réclamant une victoire aérienne à bord de son F-104 contre un Mystère IV indien. Cette victoire, contestée par les Indiens, serait la première victoire aérienne d'un appareil capable d'atteindre Mach 2 et la première victoire par missile de la force aérienne pakistanaise (Pakistan Air Force ou PAF).
La PAF perdit un F-104 pendant les opérations de 1965 tout en réclamant deux victoires sur des avions indiens.
Un Starfighter serait à l'origine de l'interception d'un Gnat de la Force aérienne indienne le 3 septembre 1965. Des F-104 ont été dirigés vers le Gnat qui volait au-dessus du Pakistan alors qu'il retournait vers sa base d'origine. Les passages supersoniques très rapprochés des F-104 forcèrent le pilote du Gnat à se rendre, descendre son train d'atterrissage et atterrir sur un terrain pakistanais désaffecté. Les Indiens prétendent que le Squadron Leader Brij Pal Singh fit une erreur de navigation qui l'obligea à se poser sur ce terrain pakistanais. Il fut retenu comme prisonnier de guerre avant d'être relaché (il termina sa carrière avec le rang d'Air Marshall). Le Gnat indien est aujourd'hui exposé au Musée de la PAF à Karachi.
Pendant la guerre de 1971, et notamment après l'introduction du MiG-21 en Inde, le Starfighter n'était plus guère considéré comme une véritable menace. Quatre F-104 ont été perdus lors de combats avec des MiG-21. L'un des pilotes réussit à s'éjecter au-dessus de la mer, mais les secours indiens ne réussirent pas à retrouver le pilote dans les eaux infestées de requins. Un Alizé de la marine indienne fut néanmoins descendu par un F-104 pakistanais de retour d'une mission annulée.
Au même moment où le F-104 tombait en disgrâce aux États-Unis, la Luftwaffe allemande s'intéressait de très près au chasseur multirôle. Le F-104G fut présenté comme une conversion d'un chasseur temps clair en un chasseur tous temps spécialisé dans l'attaque au sol, la reconnaissance et l'interception. L'appareil trouva un marché additionnel avec les autres pays de l'OTAN, conduisant finalement à la production de 2 578 appareils de toutes versions aux USA, mais aussi et surtout sous licences dans d'autres pays. Sept pays reçurent leurs Starfighter dans le cadre du plan d'aide américain du Military Aid Program (MAP). Les réacteurs américains furent retenus et construits sous licence en Europe, au Canada et au Japon. Le siège éjectable Lockheed initialement choisi fut remplacé plus tard dans certains pays par des Martin-Baker zéro-zéro réputés plus sûrs.