在1965年4月，乔治.威尔斯加入476TFS中队，在双公羊(Two Buck)行动中开始了他第一次驾驶F-104前往越南的部署，他得为18架战斗机组织空中加油机，这是战术空军司令部最长距离的越洋飞行之一，他们途径夏威夷的希卡姆空军基地，路上进行7次空中加油。在关岛的安德森空军基地停留后抵达他们在台湾公馆(Kung Kuan，后来的清泉岗)的主要作战与维护基地。4架飞机在途中因为机械故障而放弃，在台湾歇了4天后，这14架F-104C于4月19日抵达岘港，并在第二天开始执行护航任务。
这支中队最初的其中一次飞行展示了479TFW联队接下来在东南亚两次部署期间的主要任务模式，4架F-104C各挂载了2枚M117炸弹参与了南越空军A-1在第II军责任区范围内的一次攻击行动，这次行动有南越空军指挥官阮高祺率领，12架A-1轰炸了同海附近一座可疑的兵营。南越空军把炸弹扔在了镇里，错过了目标，剩下的F-104C由霍华德.戴尔(Howard Dale)中校率领，从14000英尺高度俯冲，一系列直接的命中炸毁了这个目标。
岘港是越共工兵和火箭炮经常攻击的一个目标，就像476TFS中队接下来经历的一样。1965年7月1日，3架F-102A三角剑在停机坪上因为越共向座舱里扔手榴弹以及朝飞机的尾喷管开枪而报销，但F-104C逃过了一劫。然而，在中队抵达几天后，他们就首次遭受战伤，一架F-104C完成轰炸任务回来以后主翼受到了严重损伤。
F-104C-5-LO 56-0892挂载了2枚M117炸弹，准备起飞执行对地攻击任务----这是许多星战斗机飞行员在东南亚的主要任务。哈罗德.阿尔斯顿(Harold Alsoton)在1967年的飞行日志里写道当年2次前往岘港作战期间完成了67次遮断和道路空中侦察任务，总计136个战斗起落架次。他同样还执行了20次EB-66电子战机的护航任务，而且首次目睹了其中一架飞机被一枚SA-2导弹打下来。476TFS中队在1965年12月18日回到乔治基地，之后转移到波多黎各空中国民警卫队旗下。此机最终被陈列在卢克空军基地，用来纪念58TFTW联队的F-104G训练项目。
大眼保护者
F-104在东南亚的一个主要任务就是保护在北越海岸边上巡逻的洛克希德EC-121预警星，这种飞机用自己的监视设备和雷达为美军的飞行员提供米格机预警。美国空军一共接收了74架这种高价值的飞机，从1966年起还得到了来自美国海军的补充，加州麦克莱伦基地的552AEW&CW空中早期预警和管制联队在远东使用这种飞机。这种活塞发动机的“怀孕孔雀鱼”或“康妮(民用型客机的名字叫星座)”雷达监视机在古巴导弹危机期间就开始服役了，而且在1965年4月，美国空军于东南亚成立了它的大眼特遣队，就在第一架F-104C抵达3天前，4架EC-121D被派往台南航空站和西贡的新山一机场，这两个基地从1965年4月16日开始雷达监视巡逻。
这起初是一种美国海军的飞机，EC-121被用来保护舰队，为他们提供关于入侵飞机的早期预警。因此，它在陆地上由于地形的杂波干涉而很难获得清晰的雷达信号，尤其是在北越的山地上。它的AN/APS-45测高雷达被安装在“康尼塔”上巨大的整流罩里，在飞机上的作用距离最多只能达到70英里。这就意味着大眼机得把它们的雷达监视路径设定在距离海岸线仅30至50英里的地方，而且高度要降低到50英尺，以便飞机上的AN/APS-20(或者AN/APS-95)搜索雷达的信号被水面反射回来，这样就把发现目标的距离扩展到了150英里----这个战术是在古巴导弹危机期间被发明的。
在低空飞行同样也保护了脆弱的EC-121不被敌方的雷达发现，而且即便他们发现了大眼预警机，北越空军的管制员也会让他们的战斗机离EC-121D远远的。任何前出到东京湾上去搜索巡逻机或者加油机的时候都将面对美国海军舰载战斗机和F-104C巡逻机的拦截。
为EC-121D超级星座护航(如同照片里的这架55-0127号机，但作为RC-121D-LO来建造)占用了479TFW联队的大量战斗时间，但是这2架F-104A在战前就开始了这方面的训练。主翼衍生自凯利.约翰逊设计的P-38闪电，EC-121在越战期间起到了重要作用。尽管在越战期间没有EC-121战损，但是1969年4月15日，海军VQ-1中队的EC-121K 135749被一架北朝鲜的米格-17击落。
保护EC-121D被F-104飞行员们认为是最具挑战性的任务，在恶劣的天气或者夜里于低空飞行对于大眼机组们来说就已经够困难的了，而且速度还要在290英里/小时以下。相对速度较快的F-104C用来贴身护航显然是不可能的，因此3支星战斗机小队(四机编队)和他们的KC-135A加油机在天上设置了3道障碍战斗空中巡逻(BARCAP)路线，高度在15000英尺至20000英尺之间，将米格机阻挡在两条大眼机的巡逻路线之外。
一架EC-121D在低空靠近海岸的伊桑A(Ethan Alpha)路线上飞行，伊桑B(Ethan Bravo)路线则有50至60英里远，而且高度在10000英尺左右----由另一架飞机在更远的海上来飞(同样作为早期预警的备用机，为伊桑A路线上的预警机提供雷达预警)。伊桑B路线在1966年8月被老挝上空的伊桑C(Ethan Charlie)路线取代，北越空军战斗机借助地形掩护的拦截将很快会飞到大眼机的身边，这是无法避免的，而F-104C独特的加速使得他们能够迅速做出反应。
通常，4架F-104C被用来掩护一架EC-121D，而第3支编队跟在加油机盘旋，之后在进去替换保护伊桑B路线的战斗机，而后者则转去替换保护伊桑A路线的战斗机，并让他们回去加油。因此，每一次任务都需要12架F-104C和2架加油机，当星战斗机被更加耗油的F-4C鬼怪II取代后，加油机的数量增加到了4架。由于飞机数量不够用，护航的星战斗机小队偶尔会减少到2支。巡逻区被划分成长宽各10英里的网格区域，每个区域都用两个字母的代码表示(玩过坦克世界的应该对这种地图很熟悉)，而米格机也有颜色代码----米格-21是蓝色、米格-17是红色、米格-19(歼-6)是白色。“蓝色，Alpha Golf”意味着有一架米格-21在河内上方飞行，而2架执行战斗空中巡逻任务的F-104将立刻转向目标，同时，如果有必要的话，加油机旁边的2架战斗机将过来接替他们。
天上的F-104C每隔2.5小时就要进行一次空中加油，而且他们通过KC-135A硬管加油杆改装的软管加油锥套在5分钟的时间内完成。使用主翼下方的油箱可以让翼尖挂上2枚AIM-9B导弹。
F-104的表现在北越空军里已经是众所周知的了，而它们的声望使得北越空军的战斗机不敢去攻击稀少、昂贵和必要的EC-121D。然而，由于米格机飞行员们没有预料到会和F-104卷入空战，他们没有针对这种飞机进行专门的空战训练。就像伊斯特凡.托佩尔泽尔(István Toperczer，其作品详见译者翻译的北越米格-17&19和北越米格-21战史)评论道他采访的北越空军飞行员“他们的空战准备是针对美国空军F-4、F-105、B-52和美国海军飞机的，他们没有提到针对F-104的战术。”