F-104C的交付过程也被拖延了，主要是J79发动机和M61火神炮在安装期间出现了问题，发动机压缩涡轮叶片失效、因为发动机尾喷管“花瓣”会被卡在打开的位置上，把推力降低，加上发动机过热，这些全部都在YF-104的测试项目里出现过。1958年下达了所有F-104A停飞的命令，将改进的J79-GE-3B发动机安装到飞机上，又拖延了服役的时间。因为防务政策的迅速转变，战术空军司令部对F-104的兴趣曾一度下降。从1956年起，他们开始寻找一种更大、航程更远的战斗机，同时拥有更大的载弹量。50年代末，战术空军司令部对飞机的常规战争能力有了更多的要求，以巩固其挂载核弹或者数量更多的常规武器挂载，扩大的F-104C的对地攻击角色范围。
因此，星战斗机的数量飞限制在了77架----只够装备一支战术空军司令部的联队。如果这种飞机按照战术空军司令部的安排参与了欧洲的核战，看起来F-104C将被用于空优作战，而F-100D和F-105D才会被用于执行核打击任务。
第一架F-104C在1958年7月24日首飞，同年9月交付给乔治基地的479TFW联队476TFS中队，用于取代这支中队的F-100超佩刀。尽管仅限于乔治基地的4支中队，但星战斗机的用途远不止于此，比起战术空军司令部的策划者在1958年预料的更加活跃多变。同样交付的还有21架F-104D，这些机体在F-104C的机鼻上加了一个双座座舱，取消了M61航炮和机身中线上的固定挂架。飞机的两个座舱之间有一个更大的固定中间段，而且两个开放透明的座舱盖中间还有一个风挡，后来在一些早期的F-104B上安装了向上弹射的弹射座椅。
在总共生产的2579架各型F-104里，美国空军接收了663架，其中只有296架为美国空军自用，剩下的367架都被用于军事防务互助计划。给美国空军制造的F-104A/C产量很低，完全不是一条预计每天制造20架飞机的生产线所能达到的。F-104G是在世界其它地方使用最为广泛的一种型号，德国从1963年开始向亚利桑那州的卢克基地派出110架F/TF-104G来训练德国空军(Luftwaffe)的飞行员，这些更重更复杂的F-104G带着4个副油箱和一个侦察吊舱仍旧可以在低空以近600节的速度巡航一个小时，降落后还有1000磅余油。这些F-104G使用美国空军的标识和编号，但同样也使用“影子”德军编号。这架F-104G 67-14892(影子编号24+48)后来被转交给台湾空军，改装成RF-104G后于1993年3月4日坠毁。
F-104D同样有一个空中加油管，并安装了一台了推力为15800磅的J79-GE-7发动机，后者是通用动力、战术空军司令部、俄克拉荷马市航空材料中心在1960至61年改善F-104和J79发动机搭配项目的研究成果，使用了新的涡轮叶片。
每一支F-104C中队通常拥有2架F-104D，用于换装和专业化训练，它们的速度和爬升都能与单座型相媲美。
洛克希德在F-104上投入了巨资，而且美国空军订购了296架这种飞机----相比起其它的百系列战斗机要少----很令人失望。因此，这家公司迫切地寻求改进这种飞机的新方法来满足改变后的要求，基本上就是将其变成一种更加复杂的战斗轰炸机。这就违反了凯利.约翰逊最初设计时的“轻巧、快速和简单”的原则，但同样能使得飞机适应北约国家作为截击机、战斗轰炸机和侦察机的角色，主要是针对西德空军。在这些空军里，以及给日本、加拿大和其他国家的空军都在不断寻求新机种来取代向F-84和F-86这样的第一代战斗机。
在本书描述范围以外的那些方法里，基本型的F-104C/D很快就变成了一种更强、更重(大约1000磅)更复杂的F-104G战斗机，成为了这家公司最好的外销产品。到了60年代中，一共有15个国家的空军在使用星战斗机----比任何其它的美制战斗机都要多----其中有7个国家在进行专利生产，这些国家的航空企业在生产F-104的时候得到了巨大的好处“它把很多空军到带入了现代，而且得到财团资助后继续生效的欧作战飞机一直到现在还在服役。”汤姆.贝克(Tom Baker)少将解释道(他曾经是德国空军F-104飞行员的换装训练教官，也曾任英国雷肯赫斯基地48TFW的联队长)，“在欧洲，F-104使用者之间展开的一系列会晤对于加强欧洲的空军整体力量起到了重要作用。”
总计有2578架各种型号被生产出来，最后一架给意大利空军的F-104S于1979年3月出厂，美国空中国民警卫队继续使用一些空军的早期型号至1975年7月31日，而中华民国空军(Republic of China Air Force：中国台湾空军)的F-104在1998年5月退役。过了8年后，意大利空军的F-104直到2005年7月27日才退役，结束了自进入美国空军现役后长达42年的截击机服役生涯。这明显力压了所有其它百系列战斗机的服役记录，其中包括1988年才退役的F-106三角标枪。
F-104实现了战术空军司令部里最佳空优战斗机的独特运用，而且也是唯一一种在古巴危机和越战期间完全适合空战角色的战斗机。它在美国空军里相对较短的服役的一部分原因是资助F-15鹰研发的压力结果，这种美国空军的空优战斗机最终服役了30多年。