Năm 1841, nhân việc biên phòng mỗi ngày một cấp bách, vua Minh Mệnh giao cho ông giữ chính quyền hai tỉnh Quảng Nam và Quảng Nghĩa(3).
Vào đến Đà Nẵng, xem qua địa thế, Nguyễn Tri Phương lập tức dâng sớ về kinh:
“Đà Nẵng là một hải cảng có thể trở nên quan yếu, phải đắp nhiều đồn lũy, phải đặt thêm nhiều pháo đài, nhiều súng ống để phòng bị nạn ngoại xâm”.
Được vua chuẩn y, lập tức ông sửa sang thành lũy, đóng chiến thuyền, chỉnh đốn các cơ quan trị an trong tỉnh. Vua ban thưởng cho ông, triệu ông về kinh lĩnh chức tham tri bộ Công. Nhưng không được bao lâu thì vua Minh Mệnh băng hà.
Vua Thiệu Trị lên ngôi, bổ Nguyễn Tri Phương vào tổng đốc An Hà (Nam kỳ). Hồi ấy, bọn thổ phỉ dấy loạn ở phủ Ba Xuyên, tỉnh An Giang (Sốc Trang)4. Quan tổng trấn Sốc Trang Dương Văn Phong, hành quân kém cỏi, đã bao lần bó tay thua giặc, đệ sớ về kinh xin quân cứu viện, nên vua Thiệu Trị mới cử Nguyễn Tri Phương vào Nam kỳ.
Lúc ông lên đường, nhà vua thân giao chiếu chỉ cho ông và ân cần dặn:
“Khanh hãy giữ một dạ trung thành. Sai khanh đi như thế này, tức trẫm giao cho khanh việc vào sinh ra tử, khanh nên gắng sức để yên lòng trẫm”.
Ông cảm động lĩnh chiếu chỉ, lui về nghỉ ngơi ba hôm, rồi cất quân lên đường. Vào đến nơi, ông thương nghị với quan Chưởng vệ Nguyễn Lương Nhàn:
“Quân ta mới đến, nhuệ khí còn hăng cần phải giao phong gấp mới mong đuổi được giặc”.
Lại sợ đám tàn quân bại trận của viên tổng đốc Dương Văn Phong ngày trước sẽ gieo nỗi thất vọng cho quân ở kinh mới kéo vào, ông thân hành đi các đồn lũy, dùng lời nghĩa khí, kích thích lòng quân. Khi biết đích rằng mọi người đều một dạ trung thành và can đảm theo hiệu lệnh của chủ tướng, ông liền chia đội ra làm ba đạo quân, cùng với bọn thổ phỉ ở Trà Tân, Sốc Trang, huyết chiến suốt mấy đêm ngày. Ông thắng trận. Tiếng súng vừa ngớt5, ông tiếp được tin ở Ba Viên cho hay bọn tàn quân đang đốt phá các đồn lũy ở bờ biển Hà Tiên.
Ông tức tốc giao cho quan Chưởng vệ Nguyễn Lương Nhàn đem binh cứu viện, rồi thân hành dẫn đại đội qua sông Vĩnh Tế, dựng đồn lũy để tiếp viện; ông đánh tan giặc ở núi Tượng, rồi kéo quân về Ba Xuyên, hợp với Tôn Thất Nghị đánh Sốc Trang. Hiểu rõ chiến thuật, hết lòng yêu mến và kích thích quân sĩ, ông chỉ huy quân đội đến đâu, được thắng trận đến đấy.
Các tin ấy về kinh, vua Thiệu Trị ân tứ cho ông nhất hạng kim tiền và nhiều lần, giữa lúc đông đủ đình thần, nhà vua đã không quên khen ngợi, nhắc đi nhắc lại với quan phụ chánh Trương Đăng Quế cái chí anh hùng, lòng hy sinh hiếm có của Nguyễn Tri Phương.
Trong năm ấy, ông cùng với Nguyễn Tấn Lâm, Tôn Thất Nghị, rời6 đại quân qua Lạc Hòa để tiến đánh giặc Mọi ở hai miền Tiền Giang và Hậu Giang. Đánh hơn mười trận, ông thắng cả, cướp được đồn lũy của giặc, lấy lương thực đem cấp phát cho bần dân.
Đầu đảng giặc là tướng Tàu Lâm Sâm, thu thập tàn binh về ẩn núp ở Đằng Lầm, Cầu Lũy, hợp các tướng sĩ, chỉnh đốn binh mã, liều chết để chống cự với Nguyễn Tri Phương. Ông được tin này, biết rõ cơ mưu của giặc, mộ thêm lính tráng, hợp với các đạo quân, rốc7 sức phá tan những nơi hiểm yếu của giặc. Thế là không mấy lúc, ông đoạt lại những miền Lâm Sâm chiếm cứ.
Lúc ông đánh Lạc Hóa, vua Thiệu Trị có ban cho ông một bài thơ, lời lẽ vô cùng thống thiết:
雨洗兵銷恊所云
Vũ tẩy binh tiêu hiệp sở vân
佳章連接捷馳聞
Giai chương liên tiếp tiệp trì văn
攻其無備良謀將
Công kỳ vô bị lương mưu tướng
勇各爭先不撼軍
Dũng các tranh tiên bất hám quân
烏合三千皆魄散
Ô hợp tam thiên giai phách tán
黄池百柵盡屍分
Hoàng trì bách sách tận thi phân
乘機破竹收全勝
Thừa cơ phá trúc thâu toàn thắng
樂化移師建大勲
Lạc Hóa di sư kiến đại huân.
Dịch:
Mưa giội quân tan tiếng đã đầy
Bao tin thắng trận tiếp liền tay
Đánh khi bất ý mưu khôn địch
Tiến trước ba quân chí chẳng lay
Ô hợp ba nghìn kinh mất vía
Hoàng trì trăm trại chất đầy thây
Chẻ tre thừa thế thu toàn thắng
Lạc Hóa công cao ắt ở đây.
Tuy nhiên, mầm loạn vẫn chưa trừ được hẳn, vì chính phủ Xiêm vẫn ngầm giúp các dư đảng ở Lạc Hòa, Ba Xuyên.
Qua năm sau, Thiệu Trị thứ 2, được tin báo quân giặc đã kéo qua các sông Vĩnh Tế, Tiền Giang và Hậu Giang ở Hà Tiên, ông liền từ An Giang lập tức cầm quân đuổi đánh bọn phiến loạn.
Ở Huế được tin, vua Thiệu Trị liền xuống lời khen:
“Như thế là Nguyễn Tri Phương đã giúp trẫm trừ một mối lo về phía Nam”.
Vua ban thưởng cho ông quân công nhất cấp, kim cương, liên châu và một chiếc đồng hồ quả quít - một món bảo vật hiếm có thời bấy giờ.