Nổi dậy cộng sản Sarawak
Đối đầu Indonesia-Malaysia

Do chính phủ Sukarno có thái độ thù địch với Anh Quốc và Malaysia, Tổ chức Cộng sản Sarawak sử dụng lãnh thổ của Indonesia trên đảo Borneo làm căn cứ kiến thiết một lực lượng du kích. Những người cộng sản lưu vong này sau đó tạo thành hạt nhân của hai cơ cấu du kích của Đảng Cộng sản Bắc Kalimantan: Lực lượng Du kích Nhân dân Sarawak (SPGF—Pasukan Gerilya Rakyat Sarawak (PGRS)) và Quân đội Nhân dân Bắc Kalimantan (PARAKU). Lực lượng Du kích Nhân dân Sarawak được thành lập vào tháng 3 năm 1964 tại Gunung Asuansang thuộc Tây Kalimantan với trợ giúp từ Bộ Ngoại giao Indonesia. Những lãnh đạo của Lực lượng Du kích Nhân dân Sarawak gồm Hoàng Kỉ Tác, Dương Thụ Trung, và Văn Minh Quyền. Theo Conboy, số thành viên của Lực lượng Du kích Nhân dân Sarawak là khoảng 800 và đặt căn cứ tại Batu Hitam thuộc Tây Kalimantan, với một đội ngũ 120 người từ cơ quan tình báo Indonesia và một lực lượng nhỏ cán bộ được đào tạo tại Trung Quốc. Đảng Cộng sản Indonesia cũng hiện diện và dưới quyền một nhà lãnh đạo gốc Ả Rập tên là Sofyan. Lực lượng Du kích Nhân dân Sarawak tiến hành một số vụ đột kích vào Sarawak song giành nhiều thì giờ hơn vào phát triển lực lượng ủng hộ họ tại Sarawak. Các lực lượng vũ trang Indonesia không chấp thuận bản chất cánh tả của Lực lượng Du kích Nhân dân Sarawak và thường tránh xa họ.
Trong khi đó, Quân đội Nhân dân Bắc Kalimantan do Hoàng Kỉ Tác thành lập gần Sungai Melawi tại Tây Kalimantan với trợ giúp từ Đảng Cộng sản Indonesia vào ngày 26 tháng 10 năm 1965. Trong khi Lực lượng Du kích Nhân dân Sarawak nằm dưới quyền chỉ huy của Dương Thụ Trung hoạt động tại miền tây Sarawak, thì Quân đội Nhân dân Bắc Kalimantan hoạt động tại miền đông Sarawak. Quân đội Nhân dân Bắc Kalimantan ban đầu nằm dưới quyền chỉ huy của Lâm Hòa Quý, kế tiếp là Hoàng Kỉ Tác. Theo Kenneth Conboy, Soebandrio họp với một nhóm gồm các lãnh đạo cộng sản Sarawak tại Bogor, và Abdul Haris Nasution phái ba huấn luyện viên từ Tiểu đoàn 2 Kopassus đến Nangabadan gần biên giới Sarawak, tại đó có khoảng 300 học viên. Vài tháng sau đó, hai trung úy cũng được phái đến đây.
Người Indonesia lên kế hoạch sử dụng những người cộng sản Sarawak làm một mặt trận bản địa cho các hoạt động của họ trong cuộc đối đầu với Malaysia. Nhằm hỗ trợ cho âm mưu này, họ thậm chí còn đặt tên cho tổ chức là Quân đội Quốc gia Bắc Kalimantan (TNKU), nhằm liên kết Tổ chức Cộng sản Sarawak với những phiến quân Brunei trước đó. Trong những cuộc đột kích đầu tiên thường bao gồm các thành viên Tổ chức Cộng sản Sarawak, song họ thường do một sĩ quan chính quy hoặc hạ sĩ quan của Indonesia lãnh đạo. Sau một nỗ lực chính biến của những thành phần thân Đảng Cộng sản Indonesia trong quân đội Indonesia vào tháng 10 năm 1965, Tướng Suharto đoạt quyền và tiến hành một cuộc thanh trừng những thành phần cộng sản. Những người cộng sản Sarawak mất đi một nơi an toàn và quân đội Indonesia sau đó hợp tác với Malaysia trong các hoạt động trấn áp cựu đồng minh. Theo Porritt, cuộc thanh trừng chống Cộng tại Indonesia cũng kèm theo một cuộc tàn sát do người Dayak lãnh đạo nhằm vào người Indonesia gốc Hoa tại Tây Kalimantan, hành động này nhận được sự ủng hộ cầm từ nhà cầm quyền Indonesia.