Çin ve Sovyet doktrin ve konseptlerine göre eğitim görüp harekat icra eden ve anılan ülkelerin silah sistemleriyle teçhiz edilmiş Kuzey Vietnam hava kuvvetlerinin başlıca savaş uçakları MiG-17, MiG-19, J-6 (MiG-19'un Çin yapımı kopyası) ve MiG-21 idi. Anılan uçaklar CAP ve önleme görevlerinde yer istasyonunun yönlendirmesine ihtiyaç duymaktaydılar (GCI), yani yer radarlarının verdiği komutlara göre rota ve irtifa bilgileri alıyorlardı. F-4 Phantom II ve F-105 Thunderchief saldırı paketlerine refakat eden F-104'lerin (ya da F-104 olarak teşhis edilen uçaklar) tespit edilmesi durumunda Kuzey Vietnam uçakları bölgeden uzaklaştırılmaktaydı. Bu taktik, az sayıda bir kaç olay dışında, Kuzey Vietnam MiG'leri ile F-104C'lerinin karşılaşmasını önlemiştir.
Kuzey Vietnam MiG'lerinin F-104'lerle karşılaşmaktan kaçınması üzerine bazı taktikler geliştirilmiştir. Bunların başında "Wolfpack" taktiği gelmektedir. Buna göre F-4 veya F-105 saldırı kollarına refakat eden F-104C'ler de aynı bu uçaklar gibi hız ve irtifa profillerini takip ederek radarda av-bombardıman uçağı izlenimi vermiş, dolayısıyla GCI tarafından yönlendirilen MiG'leri üzerlerine çekmeye çalışmışlardır. Anılan taktik MiG'leri çekme konusunda başarılı olmuşsa da, görüş menzili dahiline girildiği anda hız ve manevra kabiliyeti avantajını kullanan MiG'ler muharebe sahasından uzaklaşmıştır.
Düşmanla angajmana girme sorunu yaşayan F-104 filolarına 1967'den itibaren av-bombardıman, silahlı keşif ve yakın hava desteği (CAS) görevleri verilmeye başlanmıştır. Tırmanma sürati yüksek olan F-104C'ler emir geldikten kısa süre sonra havalanıp görev bölgesine çabuk biçimde intikal edeibliyorlardı, ki pilotların ve yer birlikleriin CAS görevleri için uzun süre F-104C'leri tercih etmiş olmasının sebebi budur. Söz konusu görevler için 20mm M-61 topuna ilaveten standart olarak 2 adet 750 librelik Napalm veya genel maksat bombası taşınmaktaydı.
ABD Hava Kuvvetleri Vietnam'daki harekatlar esnasında çoğu SA-2 ateşi sebebiyle olmak üzere toplam 14 adet F-104C kaybetmiştir. Bu kayıplardan en ilginci 20 Eylül 1965'teki olaydır. Bir EC-121 tarafından Tonkin Körfezi'nin kuzeyine yönlendirilen F-104C, yönünü şaşırarak Hainan Adası civarına kadar uçmuş, Çin Hava Kuvvetleri'ne ait bir J-6 tarafından düşürülmüştür. Pilotu arama-kurtarma çalışmalarına destek olmak üzere havalandırılan iki F-104C ise kötü hava koşulları ve düşük görüş seviyesi nedeniyle çarpışarak düşmüşlerdir.
1967'den sonra gerek yakın hava destek görevleri için daha uygun uçakların kullanılması, gerekse av-önleme, refakat görevleri için de alternatiflere (F-101 Voodoo, F-8 Crusader gibi) yönelinmesi nedeniyle F-104C'ler Vietnam'dan çekilmiştir. Dolayısıyla Starfighter'lar kısa süre de olsa Güneydoğu Asya'da aktif olarak ileri hat görevlerinde kullanılmışlardır. Her ne kadar Kuzey Vietnam MiG'leri ile karşılaşma fırsatı bulamamışlarsa da, varlıkları harekat bölgesini düşman uçaklarından temizleyerek dost saldırı uçaklarını rahatlatmıştır. İlaveten CAS görevlerinde de olağanüstü büyük harbe hazırlık oranı (90%'dan fazla) yakalanarak dost yer birliklerine önemli destek sağlanmıştır.