Organisasi ini sering dirujuk oleh ahli-ahlinya sebagai Pergerakan Komunis Sarawak dan seterusnya Parti Komunis Kalimantan Utara selepas tahun 1970. Dokumen-dokumen yang diterbitkan oleh kerajaan kolonial Sarawak dan Malaysia cenderung untuk melabelkan semua kumpulan anti-penjajah yang beroperasi di Sarawak sebagai sama ada Organisasi Komunis Klandestin (CCO) atau Pertubuhan Komunis Sarawak (SCO). Berikutan Perang Dingin, kumpulan anti-penjajah dan individu yang tersisa sering dikategorikan sebagai komunis oleh pihak berkuasa. Menurut akademik Jepun, Fujio Hara, dua formasi tentera utama NKCP ialah Pasukan Gerakan Rakyat Sarawak (SPGF) atau Pasukan Gerilya Rakyat Sarawak (PGRS), dan Tentera Rakyat Utara Kalimantan (NKPA) atau Pasukan Rakyat Kalimantan Utara (PARAKU). SPGF dikendalikan di barat Sarawak manakala NKPA dikendalikan di timur Sarawak. Di samping itu, organisasi komponen utama ialah Liga Pembebasan Sarawak (SLL), Persatuan Belia Sarawak (SAYA), dan NKPA.