正是这个关键性的时候，司马迁奉使前往西南夷地区，这时当地已建立了五个“初郡”：在邛国的都城建立了越雋郡，在笮国的都城建立了沈黎郡，在且兰都城建立了牂牁郡、在冉都城建立了汶山郡，在广汉（今四川梓潼）、西白马（今甘肃康县）等小邦建立了武都郡。这些初郡羡慕汉朝高度发达的封建文化，希望获得汉朝的先进技术。所以朝廷才派知识渊博、才华横溢的司马迁前去落实政策、慰问百姓。
司马迁这一次带领一百多名侍卫，以郎中将的身份，浩浩荡荡地登上了去西南的路程。从长安出发，经过汉中以后，路便难走起来，只有一条栈道，盘桓在崇山峻岭之间。从关中到巴蜀，本来无路可通，直到秦惠文王为征讨巴蜀，才命令大将司马错开凿了这条栈道。后来秦王朝对这条栈道做了一些休整，汉武帝即位后，为经营西南夷，又专门派人对栈道进行维修和加固，并在途中设置了若干个驿站，供出入巴蜀的汉家使者休息和换乘驿马。栈道外虽然设置了扶手栏杆，但险要处下临深渊万丈，朝下看去，仍给人以头晕目眩之感。最危险的地方当然是褒斜道，这是巴蜀通往关中的惟一出口。褒斜道上方两峰对峙，关隘在两峰之间，关隘之下便是几百米高的陡峭石壁，人们在石壁上凿出石梯，让人拾级而上。此处真有一夫当关，万夫莫开之势。经过二十多天的跋涉，终于达到巴郡（今重庆北），稍事休息，便风尘仆仆，赶到犍为郡（今四川宜宾）。
新任不久的犍为郡守见天子的使者来了，连忙摆酒洗尘，席间，新郡守向司马迁汇报了前不久汉朝使臣和前任犍为郡太守被且兰国王杀死的经过：
那被杀的汉朝使臣名叫驰义侯遗，他奉朝廷之命，征发西南夷的兵马讨伐南越，他偕同前任犍为郡太守，前往且兰国征兵，且兰国王不但不发兵，反而对部下说：“南越国已经杀了汉使，我们应学样。”于是暗地埋伏兵马，突袭天子使臣，驰义侯遗猝不及防，和前任犍为郡太守一同被杀。朝廷立刻派兵进攻且兰，但路远兵少，一时未攻下，这时，有两位中郎将郭昌和卫广，带领八校尉兵，在攻灭南越国之后，回师攻打且兰，这八校尉兵是特种部队，其番号分别为中垒、屯骑、步兵、越骑、长水、胡骑、射深、虎贲，擅长山地、丛林作战，勇猛无敌，所向披靡，且兰国的士兵怎能抵挡？一上阵就被八校尉兵打散，领队的且兰国王也被擒拿处死。目前且兰国无主事之人，局面不稳，亟待朝廷钦差前往安抚。
司马迁听了，知道事不宜迟，便告辞犍为郡太守，快马加鞭，赶到且兰国境，会见当地豪杰贵人和百姓代表，对他们说：“朝廷施恩给且兰百姓，不计较以往，已将且兰国改成牂牁郡，你们立即推举一人为郡守，由我钦差任命。”代表们当即推出一位德高望重的父老，为郡守人选，司马迁审察后，授予他委任状和大印。并赐予牂牁郡地图，其疆域包括今贵州中部以南地区，云南东南部地区、广西自治区西北部地区，郡治在今贵州贵定东北。
司马迁抚慰好且兰地区后，立即向邛都出发。邛都位于滇北，这一带大大小小有十几个土邦，以邛都国最大，土邦的头人都看邛都国君的脸色行事。前不久，邛都国君见且兰国杀了汉使，也大胆学样，杀了驻在那儿的汉朝使臣，于是，其他小邦也学着拦劫汉朝官商。朝廷闻知，同样派八校尉兵前往镇压，将邛都国君斩首。此处情势混乱，百姓生活困苦。
从且兰到邛都，要经过许多山地，在山峦环抱中，不时出现盆地，这些盆地自然就成为人们聚邑而居之地，平坦之处都被乡民辟为农田。
夜晚，一行人在帐篷里休息，司马迁坐在中帐之中，秉烛沉思。他想：“开西南夷道真是一项劳民伤财的举动。汉武帝年轻气盛、好大喜功，唐蒙等臣子则察言观色、曲意迎合，以求升迁和宠幸，才使汉朝的军民陷入西南这个泥沼。”他将这种想法和几个随从说了，左边的一个侍卫说：
“是呀，这真是个泥沼，由于道路不通，大军很难开到这个地方来，即使来了，运送军队的给养，千里迢迢，花费大大超过实效。被征发的百姓负担太重，结果引起民变，临时又得运兵来镇压。这么一来，就是把巴蜀全部的租赋都花费上去，也抵不了开西南夷道的费用。”
左边的一个侍卫说：“现在朝廷万不得已，只好将一些犯罪的囚徒送到这儿，让他们当屯垦兵，以充实边塞。结果耕种所得归地方所有，而行政支出却要算在中央朝廷头上。这也是得不偿失之举啊！”
司马迁说道：“你们说的都是事实，但我们既然已经来到此地，就得将事情办到底。不管结果如何，我们做事对得起朝廷和百姓就行。”
第二天，他们来到邛都国，周围的土邦首领听说天子的使臣到了，都前来磕头请罪，他们不想遭到邛都国君一样的下场，愿意诚心归附汉朝。司马迁责令其一一写悔过书，然后饶恕了他们拦杀汉朝官商的罪过。随即司马迁向他们宣布邛都国已改为越雋郡，不再是一个独立的小国了，他们必须解散私家军队，服从新来的郡守管束，做汉朝的顺民。司马迁还让新郡守和大家见面，划定了越雋郡的范围，其地包括今天的四川西昌地区、凉山彝族自治州、云南西北部分地区，郡治在今四川西昌市东。
司马迁还和郡守一起开仓救济贫民，饥民每人发给两斗玉米，又采购了当地的特产竹杖，运回长安。
然后司马迁一行来到笮国的都城。笮国的君主名叫巴莫，生性残暴，稍不如意，就要挖掉平民百姓的眼睛，割断人的腿筋，又酷爱女色，只要他看中的女子，不管是不是已有夫家，他不弄到手决不罢休。他已有四十九个妃子，却还要夺取弟弟桑巴的未婚妻，为达到目的，派人暗杀桑巴，幸而桑巴警惕性高，逃到邻近的冉国，摆脱了他的追杀。
巴莫一直仇视汉朝，常常截杀汉朝的官商，这次，乘且兰、邛都等国杀汉朝使臣之风，也将驻笮国的汉使杀死。不久前，八校尉兵来到，巴莫恶贯满盈，获得应有的下场，被当众处死。
司马迁在笮国处理善后，正式宣布在当地建立沈黎郡，地域包括今四川雅安、汉源一带，郡治在今四川汉源东北。任命桑巴为郡守。
随即冉国王的使者来到，表示愿意取消独立，请求做汉朝的臣民，司马迁代表朝廷接受其请求，改冉国为汶山郡，辖地在今四川茂汶羌族自治县一带，郡治在茂汶县北。由原国王担任郡守。汶山郡处于地震带，常发地震，司马迁告诫当地官民注意防震抗震。
随即司马迁又派副手去西白马等小邦，安抚那儿的边民，正式宣布建立武都郡，任命郡守，将今天的甘肃南部的武都地区和陕西西南部分地区划入该郡范围，郡治在今甘肃西和县西南。
司马迁办好以上初郡的任命、抚慰事务后，便向最后一个要访问的独立国——滇国前进。
从笮国到滇国有千里之遥，其间要渡过若水和绳水两条大河，更要翻越无数的崇山峻岭。沿途自有说不尽的异族风光。
他们来到一个十分险恶的地区，到处都是高山、丛林和毒蛇猛兽，时不时从丛林中涌出一伙野蛮人，上身不穿衣服，下身裹着布片草绳，据说是劳深、靡莫等部落的人，奉其酋长之令，前来拦截朝廷使者，夺取钱财，谋害性命，司马迁手下的几个向导就被这些土人射杀，司马迁和部属们计议，决定暂时撤退到安全的地方，然后向后方请求援兵。他们在一个安全的村落住了十余天，援兵来到，驱除了这些野蛮的土人，让朝廷使团安全通过。这支援兵队伍一直护送他们到达滇国都城，才返回。
见到滇王后，司马迁向他陈述利害：滇王如归附汉朝，称臣纳贡，可得到汉朝的许多物资援助，如不归附，则汉朝大军到来，就会将滇国灭掉，夷为郡县，且兰、邛都、笮等国国王违抗汉朝的命令，杀汉朝使臣，不是全被诛灭了吗？而夜郎国愿意诚心归附，仍让其维持小国体制。何去何从，请大王自己斟酌选择。
滇王答道：他原以为汉国只有滇国这么大，现在看过司马迁钦差大臣提供的地图，才知道汉国比滇国大许多倍。滇国是小国，但离汉国最远，汉国鞭长莫及，即使动兵戈来征伐敝邦，也徒然耗费人力物力。汉国为什么不能让敝邦独立存在，平等共存，互通友好呢？
司马迁见滇王说的也有道理，就不勉强他立刻归附，一切容以后再议。当即告辞滇王，踏上了返归巴蜀的道路，滇王特地派兵丁护送他们，让他们平安到达笮国后，护送的滇兵才回滇复命。
总结起来，司马迁这一次到了且兰、邛、笮、滇国、昆明等地，巡视新归附的地区，告喻父老，任命官吏，他跑遍了祖国的大西南。
一路上，司马迁牢记出使西域的前辈张骞的指教，因而十分注意搜集沿途的地理、经济、人文方面的资料。面对祖国秀丽的山川，他常常不顾旅途劳顿，进行各项考察工作，就像当年漫游大江南北一样，不忘搜集史料。路过李冰父子治水兴筑的都江堰，他在那里停留了几天，进行勘察和访问。走到陌生的地方，每晚休息以前，他找来当地土人老乡，询问当地的物产、民俗、文物等，并一一记载下来。
司马迁此行，任务本是在大规模军事行动之后设置郡吏，所以班固在《汉书》中给予了很高的评价，把司马迁和丞相公孙弘并论。司马迁圆满完成安抚西南夷的任务，赢得了汉武帝的信任，为以后的仕途奠定了一定的基础，他的官阶也从三百石升至一千石。
两年后，武帝元封二年（公元前109年），汉朝发巴蜀兵击灭劳深、靡莫等部落，又兵临滇国，滇王请求归附，愿意接受汉朝的官吏来滇国，并答应入长安朝见天子。汉武帝在该地区设置益州郡，辖地包括今云南西北部地区和中部地区，郡治在今云南晋宁县东，赐滇王王印，让他继续统治这一地区。
