Trước khi diễn ra các cải cách của vua Minh Mạng, tháng 10 ÂL năm 1832, Nguyễn Văn Quế, quản lý biền binh thành Gia Định thời Lê Văn Duyệt và quyền lĩnh ấn Tổng trấn Gia Định thành sau khi Lê Văn Duyệt mất, được bổ làm Tổng đốc An - Biên (tức liên tỉnh Phiên An và Biên Hòa), cơ chế cắt đặt quan cai trị cũng tương tự như liên tỉnh Long - Tường ở bài trước.
Quản lý biền binh thành Gia Định thời Lê Văn Duyệt là Nguyễn Văn Quế đóng ở phủ Tân Bình thuộc tỉnh (lớn) Phiên An, kiêm Tuần phủ, dưới có Bố chánh Phiên An (bấy giờ là Bạch Xuân Nguyên). Quan Hiệp trấn cũ của trấn Biên Hòa là Vũ Quýnh được bổ làm Bố chánh tỉnh (vừa) Biên Hòa, thự lý (署理: tạm trị, tạm nhận) ấn quan phòng của Tuần phủ tỉnh này.
Đối với liên tỉnh An - Hà, gần hai tháng đầu cải cách không có Tổng đốc mà chỉ có Tuần phủ kiêm hạt và kiêm luôn cả việc bảo hộ nước Chân Lạp, người đầu tiên được bổ nhiệm là Ngô Bá Nhân (còn gọi là Nhơn) làm thự Tham tri Binh bộ Tuần phủ tỉnh (vừa) An Giang, kiêm quản tỉnh (nhỏ) Hà Tiên và Chân Lạp. Mỗi tỉnh lần lượt có Bố chánh, Án sát và Lãnh binh, mỗi chức một viên. Bố chánh Hà Tiên là Phạm Xuân Bích thự lý ấn quan phòng Tuần phủ tỉnh này. Cuối tháng 11 ÂL năm 1832, vua Minh Mạng bổ Lê Đại Cương (nguyên Tổng đốc liên tỉnh Sơn Tây - Hưng Hóa - Tuyên Quang) làm Tổng đốc An - Hà kiêm lĩnh ấn “bảo hộ Chân Lạp quốc”.
Tháng 8 ÂL năm 1833 vua Minh Mạng cho đổi tên tỉnh Phiên An thành Gia Định, liên tỉnh An - Biên sau đó gọi là Định - Biên. Vua dụ rằng: “Nguyên sáu tỉnh Nam kỳ, đều gọi chung là Gia Định. Đó là do Hoàng khảo Thế tổ Cao hoàng đế ta [chỉ vua Gia Long], đặc ơn ban cho tên tốt ấy.
Từ khi nổi lên ở miền đông thổ đến giờ, nhân dân sở tại từ lâu được yên trong cảnh vô sự. Năm ngoái, chia đặt tỉnh hạt, nhân đó đổi trấn Phiên An làm tỉnh Phiên An. Gần đây, nghịch [Lê Văn] Khôi giữ thành làm phản, dần đã dẹp yên, nên đổi là Gia Định để lấy lại cái tên tốt ấy, khiến cho nhân dân thuộc tỉnh từ đây về sau, đều được hưởng phúc thái bình lâu dài” (Đại Nam thực lục, tập 3, sđd, tr.696).
Thời vua Minh Mạng, Đại Nam trải qua nhiều thay đổi, ông tiến hành các cải cách về kinh tế, chính trị, quân sự, văn hóa giáo dục nhưng có lẽ cuộc cải cách hành chính năm 1831-1832 ở các địa phương từ tỉnh xuống đến tổng, xã là một trong những dấu ấn quan trọng của vị hoàng đế này trong 20 năm trị vì đất nước. Một cuộc cải cách hành chính với vua là trung tâm, các quan lại trên - dưới kiểm soát và kiềm chế lẫn nhau, xóa bỏ quyền lực địa phương tồn tại 1/4 thế kỷ.
Tháng 5 ÂL năm 1834, vua Minh Mạng đặt tên gọi cho “Nam Bắc trực, Tả Hữu kỳ và Nam Bắc kỳ (Quảng Nam, Quảng Ngãi là Nam trực; Quảng Trị, Quảng Bình là Bắc trực; Bình Định đến Bình Thuận là Tả kỳ; Hà Tĩnh đến Thanh Hoa (bây giờ là Thanh Hóa) là Hữu kỳ; Biên Hòa đến Hà Tiên là Nam kỳ; Ninh Bình đến Lạng Sơn là Bắc kỳ)” (Đại Nam thực lục, tập 4, nhóm dịch, NXB Giáo dục, 2007, tr.202).