Đến giữa thập kỷ 90 của thế kỷ XIX, ở khu vực Thượng du Bắc Kỳ, thực dân Pháp chuyển dần những vùng được bình định vốn đặt dưới chế độ quân quản sang chế độ dân sự để bắt tay vào khai thác, mở đầu cho sự ra đời của một loạt đơn vị hành chính cấp tỉnh. Tỉnh Sơn La ra đời trong hoàn cảnh đó.
Do có vị thế trọng yếu ở miền Tây Bắc, ngay từ năm 1886, Tổng trú sứ Trung - Bắc Kỳ đã ra nghị định chuyển châu Sơn La thuộc phủ Gia Hưng, tỉnh Hưng Hóa thành một cấp tương đương với cấp tỉnh. Đến ngày 20-8-1891, Toàn quyền Đông Dương ra Nghị định đưa địa hạt Sơn La vào địa bàn của Đạo Quan binh thứ tư (gồm: địa hạt Sơn La và các tổng tách ra từ tỉnh Hưng Hóa), thủ phủ đặt tại Sơn La. Ngày 27-2-1982, Toàn quyền Đông Dương cho thành lập Tiểu quân khu Vạn Bú (gồm phủ Vạn Yên và phủ Sơn La) trực thuộc đạo Quan binh thứ tư Sơn La.
Ba năm sau, vào ngày 10-10-1895, Tiểu quân khu Vạn Bú chuyển từ vùng đất quân quản sang chế độ dân sự và ngày này trở thành thời điểm ra đời của tỉnh Sơn La. Đồng thời, chính quyền thuộc địa nhập toàn bộ Tiểu quân khu phụ Lai Châu vào địa hạt này. Do đó, địa bàn của tỉnh Vạn Bú bao gồm: phủ Vạn Yên với các châu Mộc, châu Phù Yên; phủ Sơn La với các châu: Sơn La, châu Yên, châu Mai Sơn, châu Thuận, châu Tuần Giáo, châu Điện Biên (thuộc Tiểu quân khu Vạn Bú cũ), châu Lai, châu Luân, châu Quỳnh Nhai, Phong Thổ (thuộc tiểu quân khu phụ Lai Châu cũ).
Để ổn định và tạo điều kiện tốt nhất cho chính quyền địa phương hoạt động, ngày 7-4-1904, theo đề nghị của Thống sứ Bắc Kỳ trụ sở hành chính của Phái bộ Chính phủ Vạn Bú được chuyển từ Pá Giang đến Sơn La - nơi an toàn và có khí hậu mát mẻ.
Ngày 23-8-1904, Phái bộ Vạn Bú được đổi tên thành Phái bộ Sơn La. Từ đây tỉnh Vạn Bú được đổi thành tỉnh Sơn La. Vì địa bàn Sơn La quá rộng, địa hình lại phức tạp, khó khăn cho việc quản lý, chính quyền thuộc địa chủ trương thu hẹp phạm vi của tỉnh. Theo đó, địa hạt Sơn La còn lại 6 châu: Sơn La (hay Mường La), Thuận Châu, Mai Sơn, Châu Yên, Châu Mộc, Phù Yên (gồm cả Bắc Yên ngày nay). Năm 1932, Sơn La vẫn gồm 6 châu, 29 mường, 1.180 bản và Trung tâm hành chính Vạn Yên. Các đơn vị hành chính trên tồn tại đến hết thời kỳ Pháp thuộc.
Sự ra đời của đơn vị hành chính Sơn La thể hiện rõ vị trí chiến lược quan trọng về các mặt và cũng là kết quả của sự hội tụ và phát triển của các yếu tố tự nhiên, chính trị, kinh tế, xã hội và con người nơi đây.