Toàn tuyến biên giới phía bắc của Việt Nam
Truy quét tàn quân Khmer Đỏ (tháng 1 năm 1979 - tháng 5 năm 1979)
Trên chiến trường Campuchia, vì quân Việt Nam tiến quá nhanh chóng, nên quân Khmer Đỏ chỉ bị tan rã chứ chưa bị tiêu diệt hẳn. Nhiều đơn vị đã tập trung lại thành những đơn vị nhỏ, tiếp tục đánh du kích và quấy phá.
Sau khi Quân đoàn 4 chiếm được Phnôm Pênh, ngày 7/1/1979 các đơn vị của Quân đoàn 3, Quân khu 5 và Quân khu 7 cũng vượt sông Mekong tiến chiếm và bình định lãnh thổ phía bắc Biển Hồ và sông Tonlé Sap. Quân Khmer Đỏ đã cố gắng kháng cự gần tỉnh Battambang nhưng cũng chỉ có thể làm chậm đà tiến quân của Việt Nam. Họ đã phân tán thành nhiều đơn vị nhỏ tiếp tục đánh du kích.
Quân đoàn 2 và các sư đoàn của Quân khu 9 sau khi chiếm được vùng duyên hải cũng tiến dọc theo quốc lộ 4 về hướng Bắc. Mấy ngày sau khi Trung Quốc tiến đánh biên giới Việt-Trung, Quân đoàn 2 rút về bảo vệ Hà Nội[44]. Việt Nam bắt đầu tổng động viên, một số các trung đoàn độc lập được tăng cường lên thành cấp sư đoàn, như các trung đoàn Gia Định 1 và 2, Quyết Thắng 1 và 2, trở thành các Sư đoàn 317, 318 để gửi sang tăng cường mặt trận Campuchia. Trách nhiệm chính trong công tác hành quân vẫn là các đơn vị của Quân đoàn 4.
Ngày 8 tháng 1, Sư đoàn 10 theo lệnh của tướng Kim Tuấn thực hiện cuộc hành quân chớp nhoáng truy kích quân Khmer Đỏ. Tới ngày 9, Trung đoàn 24 đã chiếm được Kampong Thom, Trung đoàn 26 cũng đã kiểm soát được đường 6 nối Kampong Thom và Phnôm Pênh, Trung đoàn 66[f] được lệnh vượt lên trước hai đơn vị này đánh chiếm thành phố Siem Reap ở phía tây bắc biển hồ Tongle Sap. Dùng 36 xe tải chở quân, được xe tăng yểm trợ, trung đoàn nhanh chóng hành quân, tiến được 100 km chỉ trong vòng 2 giờ, đồng thời đánh tan các trạm kiểm soát của Khmer Đỏ dọc đường. Trên đường đi, một đoàn xe chở quân Khmer Đỏ cũng nhập vào đội hình trung đoàn do tưởng nhầm là tàn quân Khmer Đỏ tháo chạy. Do trời tối, không ai phát hiện ra sự nhầm lẫn này. Mãi đến khi hai bên nhận ra nhau thì một trận đánh khốc liệt mới nổ ra, quân Việt Nam tiêu diệt và chiếm toàn bộ đoàn xe gồm 23 xe tải chở quân Khmer Đỏ. Rạng sáng ngày 10, quân Việt Nam đến Siem Reap, quân Khmer Đỏ bị bất ngờ, phải tháo chạy ra bốn phía. Tới khi trời tối thì Trung đoàn 24 thuộc Sư đoàn 10 và Sư đoàn 5 của Quân khu 7 cũng đã tới nơi.
Ngày hôm sau, Trung đoàn 24 lại hành quân 100 km nữa đánh chiếm thị xã Sisophon nằm cách biên giới Thái Lan 50 km. Ngày 12 tháng 1, (sau khi trao lại thị xã cho lực lượng Quân khu 5) trung đoàn 24 một tiểu đoàn của Trung đoàn 66 cùng một đại đội xe M-113, pháo phòng không và trọng pháo theo theo đường 5 phía nam Sisophon đánh vào các lực lượng Khmer Đỏ đang tập trung về Battambang và chiếm thành phố ngay trong ngày hôm đó.
Ngày 13 tháng 3 năm 1979, tướng Kim Tuấn di chuyển Bộ chỉ huy Quân đoàn 3 đến Battambang để trực tiếp chỉ huy chiến dịch truy quét tàn quân Pol Pot tập trung ở vùng tây nam gần biên giới Thái Lan. Ba ngày sau, ông rời Battambang để đi Siem Reap, trên đường đi khoảng 40 km về hướng bắc Battambang, đoàn xe của ông bị Khmer Đỏ phục kích. Mặc dù lực lượng phục kích bị đè bẹp,[45] chiếc com-măng-ca thứ 3 có Tư lệnh Kim Tuấn ngồi bên cạnh người lái xe bị trúng đạn M79 khiến ông bị thương nặng vùng cột sống và mất ngày hôm sau, ngày 17 tháng 3. Ông là sĩ quan cao cấp nhất của Quân đội Nhân dân Việt Nam hy sinh khi tham chiến ở Campuchia. Ba tháng sau, tháng 6 năm 1979, Quân đoàn 3 của ông rời Campuchia để tham gia phòng thủ biên giới phía bắc với Trung Quốc.
Trận đánh quan trọng đầu tiên trong chiến dịch bình định diễn ra tại Kampong Speu, nằm trên quốc lộ 4 nối hải cảng Kampong Som với Phnôm Pênh, cách Phnôm Pênh khoảng 50 km. Thị xã này, sau khi quân Khmer Đỏ di tản vội vã, do Trung đoàn 10 thuộc Sư đoàn 339 Việt Nam chiếm đóng. Nhưng ít ngày sau, các lực lượng còn lại của các Sư đoàn 703, 340, 221 từ tuyến phòng thủ Svay Rieng chạy về đã tập trung lại và dự định tái chiếm thị xã. Được tin, Bộ tư lệnh Quân đoàn 4 điều động Sư đoàn 341 đến tăng cường. Trận đánh bắt đầu ngày 21 tháng 1 năm 1979 đến ngày 7 tháng 2 mới kết thúc. Dù bị tổn thất nặng, quân Việt Nam vẫn giữ được Kampong Speu, các lực lượng của 3 sư đoàn Khmer Đỏ bị tan rã, chỉ còn là những nhóm nhỏ hoặc tiếp tục đánh du kích, hoặc rút về biên giới Thái Lan.
Giữ vững được Kampong Speu, bảo đảm được giao thông trên quốc lộ 4, quân Việt Nam tiến đánh căn cứ Amleang, nơi mà bộ chỉ huy quân sự của Pol Pot từ Phnôm Pênh rút về trú đóng. Căn cứ này nằm trong một vùng rừng núi hiểm trở, cách Phnôm Pênh khoảng 100 km về phía tây nam. Lực lượng tấn công gồm Sư đoàn 2, Sư đoàn 7, Sư đoàn 9, Sư đoàn 341 của Quân đoàn 4, được tăng cường thêm Sư đoàn 5 của Quân khu 7. Vì lực lượng tấn công quá hùng hậu, quân Khmer Đỏ rút lui, bỏ lại căn cứ Amleang, nhưng họ tìm đủ cách để gây khó khăn và tổn thất cho quân Việt Nam khi họ rút lui khỏi căn cứ bằng đủ mọi cách như phục kích, bắn tỉa, gài mìn, đốt rừng...
Chiếm xong được Amleang, quân Việt Nam mở chiến dịch đánh chiếm thị trấn Leach (Phnum Kravanh). Leach là một thị trấn nằm gần quốc lộ số 5 là con đường từ Phnôm Pênh đi Battambang, cách biên giới Thái Lan khoảng 80 km. Trước ngày 7 tháng 1, Leach được Khmer Đỏ sử dụng làm căn cứ tiếp liệu. Sau khi Phnôm Pênh thất thủ, khi quân Việt Nam chưa có đủ thì giờ để chiếm đóng hết các vị trí, Khmer Đỏ dự định biến Leach thành một căn cứ phản công. Phần lớn những lực lượng còn lại được tập trung tại đây gồm nhiều sư đoàn (104, 210, 260, 264, 460, 502). Lực lượng phòng thủ cũng có vài khẩu pháo 105 ly vài xe thiết giáp.
Để tấn công Leach, quân Việt Nam đã sử dụng một lực lượng lớn và tấn công làm bốn hướng. Hướng thứ nhất, do Sư đoàn 341 thay thế Sư đoàn 330 đã bị hao hụt quân số quá nhiều khi giải tỏa quốc lộ số 5, đánh chiếm thị xã Pursat để từ đó đánh vào mặt bắc của Leach. Hướng thứ hai do Sư đoàn 9 từ căn cứ Amleang mới chiếm được đánh vào phía đông. Hướng thứ ba do Quân khu 9 phụ trách được tàu đổ bộ chở đến tỉnh Koh Kong, rồi từ đó, tấn công mặt nam. Hướng thứ tư, do Sư đoàn 31, Quân đoàn 3, từ biên giới Thái Lan theo tỉnh lộ 56 đánh ngược về mặt tây của Leach.
Vì đây là một trận quyết định, nên trận đánh đã kéo dài trên một tháng. Tất cả các sư đoàn tham chiến đều bị tổn thất nặng. Cuối cùng, căn cứ Leach của Khmer Đỏ bị Sư đoàn 9 chiếm được ngày 29 tháng 4 năm 1979. Trận đánh tại căn cứ Leach là trận đánh có quy mô lớn cuối cùng trên đất Campuchia. Sau khi Leach bị mất, các đơn vị còn lại của Khmer Đỏ rút về các mật khu ở Pailin và Tasanh sát biên giới Thái Lan. Một số khác phân tán thành những đơn vị nhỏ tiếp tục đánh du kích.
Giữa tháng 3, quân Việt Nam mở chiến dịch mới đánh chiếm căn cứ Tasanh, nằm ở phía nam Pailin. Tới 28 tháng 3, căn cứ này thất thủ, khiến cho "đại sứ quán" Trung Quốc đóng tại đây phải sơ tán về vùng núi cao. Ban lãnh đạo Khmer Đỏ tại đây cũng bỏ chạy, bỏ lại một phần tài liệu, xe cộ, vũ khí, lương thực dự trữ và 3.000 tấn đạn dược.[46]
Các đơn vị của Việt Nam bắt đầu phân nhiệm để hành quân bình định. Nhiều sư đoàn thiện chiến đã bị hao hụt nặng được rút về nước. Những sư đoàn tân lập được gửi qua tăng cường hay thay thế. Phía Việt Nam cho biết, tới cuối tháng 1 năm 1979, quân Việt Nam đã có tới 8.000 thương vong. Riêng Quân đoàn 4, đơn vị chủ lực đánh vào giải phóng Phnôm Pênh, sau 18 tháng chiến đấu (từ giữa năm 1977 tới tháng 1/1979) đã tiến hành 5 chiến dịch cấp quân đoàn, 13 trận đánh cấp sư đoàn, 68 trận cấp trung đoàn và gần 700 trận cấp tiểu đoàn, bị hi sinh 3.446 người, 12.464 người bị thương. Quân chủng Hải quân trong chiến dịch Tà Lơn đã xóa sổ lực lượng hải quân của Khmer Đỏ, làm chủ hoàn toàn vùng biển phía Nam Campuchia với tổn thất là 373 người chết, bị thương 661, mất tích 65 người.
Về phía quân Khmer Đỏ, lực lượng này bị thiệt hại rất nặng. Hầu hết các sư đoàn bị đánh tan, khoảng 3/4 lực lượng đã bị mất. Tuy nhiên, Khmer Đỏ vẫn còn khoảng 30.000 quân kịp chạy thoát sang Thái Lan hoặc trốn vào các vùng rừng núi, lực lượng này vẫn còn khả năng quấy phá, phục kích, gây mất ổn định khiến Việt Nam phải duy trì một lực lượng quân sự lớn tại Campuchia.