Sơn La là tỉnh miền núi phía Tây Bắc của Tổ Quốc có diện tích tự nhiên 14.055 km2, chiếm tỷ lệ 4,27% tổng diện tích cả nước. Địa hình chia cắt, kinh tế chậm phát triển, giao thông vận tải cách trở khó khăn nên việc thông thương ra bên ngoài chủ yếu là giao thông đường bộ và một phần đường thuỷ nội địa.
Năm 1858, thực dân Pháp xâm lược nước ta lần thứ nhất, sau khi bình định xong các tỉnh miền bắc, chúng tập trung quân tiến đánh các tỉnh miền núi thuộc địa bàn cư trú của các dân tộc ít người.
Tháng 2 năm 1886, thực dân Pháp đánh lên Tây Bắc, ngày 1/1/1888, sau khi chiếm được Tây Bắc, chúng thiết lập chế độ quân quản. Từ tháng 10 năm 1895, Sơn La chuyển sang chế độ dân sự. Thực dân Pháp sử dụng bộ máy chính quyền phong kiến để thống trị nhân dân các dân tộc, triệt để áp dụng chính sách “chia để trị” và “ngu dân” để khích động chia rẽ đồng bào dân tộc và kìm hãm nhân dân trong vòng tăm tối, lạc hậu.
Giao thông thời kỳ này, Pháp cho mở tuyến đường bộ 41 (nay là quốc lộ 6) dài 320 km, chủ yếu phục vụ cho mục đích cai trị, chuyên chở binh lính đàn áp phong trào yêu nước, cầm tù của các chiến sĩ cách mạng và phục vụ hậu cần cho chúng. Ngoài ra thực dân Pháp còn mở một số đoạn tuyến đi: Tạ Bú, đường 17, đường 43 phục vụ cho mục đích nuôi lính, quản tù chính trị.
Tổng số đường giao thông thời kỳ thực dân Pháp mở trên địa bàn tỉnh sơn La ước chừng hơn 300km, phần lớn là đường đất nhỏ hẹp, đi lại một mùa.
Sau Cách mạng tháng tám thành công, chính quyền được thành lập về Giao thông vận tải, ta tiếp tục tiếp quản giữ nguyên tổ chức cũ và những nhân viên người Việt, chính quyền cử ông Tô Thiệu Văn tham sự công chính cũ, làm Trưởng ty công chính Hoà Bình kiêm tỉnh Sơn La, trụ sở đóng ở Hoà Bình. Ông Ngô Thiệu Văn uỷ nhiệm ông Nguyễn Văn Nguyên và ông Phạm Hữu Mục là nhân viên cũ làm công tác thường trực tại Sơn La.
Giữa năm 1952 để chuẩn bị cho chiến dịch giải phóng Tây Bắc, các tỉnh Hoà Bình, Thanh Hoá được lệnh khôi phục lại cầu đường từ Việt Bắc qua Hoà Bình, Thanh Hoá được lệnh khôi phục lại cầu đường từ Việt Bắc qua Hoà Bình lên Chợ Bờ - Suối Rút Vạn Mai (cho ô tô) từ Thanh Hoá ra Vạn Mai (cho xe thô sơ) Trung ương Quyết định lập công trường 41, mở lại đường 41 khai thông từ suối Rút lên Mộc Châu về phía Sơn La do ông Bùi Văn Các Giám đốc nha Công chính - Hoả xa làm trưởng ban, ông Nguyễn Văn Nguyên được tỉnh cử ra giúp đỡ công trường.
Giữa năm 1953, trên đường 41 công trường T.A (tuyến chính) được thành lập do ông Bùi Văn Các làm trưởng ban, tỉnh Sơn La cử ông Nguyễn Văn Nguyên làm đại diện tham gia Ban chỉ huy công trường chuẩn bị mở tuyến đường từ Nghĩa lộ đến Phù Yên sang Yên Châu chuẩn bị cho chiến dịch Nà Sản. Mọi việc đang tiến hành thì địch bỏ Nà Sản nhảy dù xuống Điện Biên – Công trường T.A giải thể. Sau đó Giao thông Sơn La tiếp tục với quân dân cả nước tập trung mọi mặt chuẩn bị cho việc giải phóng Điện Biên Phủ, trong chiến dịch này Sơn La đã huy động hàng vạn dân công hàng nghìn các phương tiện vận tải thô sơ như bè mảng, ngựa thồ mở đường, vận tải chi viện cho chiến dịch.
Sau chiến thắng Điện Biên Phủ, toàn vùng Tây Bắc được giải phóng, do tình hình thực tế lúc đó, Nhà nước thành lập khu tự trị Thái Mèo (7/5/1955) gồm các tỉnh: Lai Châu, Sơn La, Nghĩa Lộ, dưới khu là các châu trực thuộc (chưa có tỉnh), các cơ quan chuyên môn cấp khu được gọi là sở, trên địa bàn Sơn La lúc đó có hệ thống các phòng giao thông các châu: Thuận Châu, Mường La, Mai Sơn, Sông Mã, Yên Châu, Mộc Châu, Phù Yên, các công trường 45, 46, đội cầu 1, 43,83 và xưởng vật tư cầu phà, hệ thống các hạt giao thông thuộc các phòng giao thông theo ngành dọc.
Tháng 12/1962 để phù hợp với sự phát triển về Kinh tế - Văn hoá - Xã hội và an ninh quốc phòng, theo sự chỉ đạo của Trung ương các tỉnh khu Tây Bắc tái lập, Sở giao thông Tây bắc giải thể. Ty giao thông vận tải Sơn La chính thức được thành lập tháng 01/1963, các đơn vị trực thuộc khu chuyển về gồm: hai đoạn quản lý và sửa chữa 1 và 2, Công ty vận tải ô tô, công trường 5, 8, Tô Múa C246, C265, C263, Công trường 312, đội cầu 43, Xưởng cầu phà, trạm vật tư giao thông, đội khảo sát thiết kế giao thông, Đội khảo sát giao thông đường sông. Ở các huyện thành lập các phòng giao thông do huyện quản lý.
Tháng 6 năm 1981 - để phù hợp với tình hình mới Chính phủ quyết định đổi tên các Ty Giao thông vận tải trên cả nước thành Sở Giao thông vận tải, Ty Giao thông vận tải Sơn La chính thức được đổi tên thành Sở Giao thông Vận tải Sơn La từ đó đến nay.