National Wrestling Alliance (1980–1985) W National Wrestling Alliance (NWA) od początku był heelem i często walczył z Donem Kernodle, który był face’em. Już na początku swojej kariery w NWA podjął kilka nieskutecznych starań o tytuły mistrzowskie. 1 września 1981 Dewey Robertson i George Wells pokonali jego i Gene’a Lewisa w walce o NWA Mid-Atlantic Tag Team Title, 30 września i 3 października Ron Bass obronił w walce z nim tytuł NWA Television Title, a 1 sierpnia 1982 Nelson odpadł w pierwszej rundzie turnieju Cadillac Tournament, po przegranej walce z Rickym Steamboatem.
W 1982 roku ówczesny posiadacz tytułu NWA United States Heavyweight Campionship Sgt. Slaughter rekrutował Nelsona i awansował go na stopień szeregowego. Od tej pory Harrel zaczął posługiwać się pseudonimem ringowym Private James Nelson. Później utworzył tag team z weteranem, szeregowym Donem Kernodle. Nowa drużyna posługiwała się nazwami Cobra Corps i The Privates (w skrócie PVT's, pl. Szeregowi). Ich głównym zadaniem było służenie jako prywatna armia Sgt. Slaughtera i pomaganie swojemu przywódcy w czasie jego panowania jako mistrza. Zespołowi dwukrotnie udało się zdobyć mistrzostwo NWA Mid-Atlantic Tag Team Championship w 1982 roku.