十九岁以前，司马迁尝到了国家对外作战初次获得胜利的兴奋和喜悦，也得到了和当时的鸿儒学习讨教的机会。因此，进入成年的司马迁，已经拥有了大国臣民的胸怀。这时的他，纯然是个盛世的骄子，拥有浪漫的个性，这使他对祖国的山河深为向往，并且早已幻想神游了。
终于，二十岁的时候，他展开了一次走遍半个中国的游历。这次游历的动机，不十分清楚，是单独一个人，还是成群结队，也没有记录可查。但有一点却是可以确定的，就是这一次大游历，对他日后完成《史记》有相当大的帮助。后面将会说到，《史记》中很多地方都有这次游历的影子，好比一个接一个的镜头在眼前闪过。难怪有人推测这次游历是奉了他父亲的指示，到东南各地收集史料去的。
关于其中经过，《史记·太史公自序》只用了五十一个字，《汉书·司马迁传》只用了四十九个字简单叙述。不过，《史记》的其他卷帙里，也常提到这次游历的所见所闻，若重新加以排列，也可以连成一系列的画面，同时可以看到一些他的思想痕迹。
那些五十一或四十九个字的叙述，只记述他游历的路线，大体是从首都到东南江淮、浙江一带，而后是沿长江下游而上溯到湖南，再转到山东，最后经河南回陕西。
首先说第一站——江淮，江淮是指今江苏省和安徽省北部一带。他来到淮阴侯韩信的故乡，故城在今江苏北部淮阴县南边。司马迁在那里专访了当地的老人，向他们询问韩信早年贫困时的种种情况。《史记·淮阴侯列传》大约在这次旅行中就有了腹稿。他在这篇传记的最后说，他到淮阴的时候，淮阴人曾经告诉过他，韩信在早年仍是个贫困平民的时候，志气就与众不同了。他母亲死的时候，他穷得没法为母亲办丧事，可是坟墓却要筑得高高的，而且占地要大，大到墓旁足够建造万家人住的房子。司马迁听了，还特地去参观那个大墓地，果然如当地人所说的那般大。他写道：“余视其母冢，良然！”
司马迁一向同情失败的英雄，在这篇列传里，开头不久，以萧何追赶韩信并向刘邦大力推荐的故事突出韩信的地位。然后描写几次战役，生动地展现出韩信的军事天才。后来则以几句“狡兔死，良狗烹”一类的话，指出韩信最后的下场。末了的“太史公曰”又很同情而无可奈何地说：“假如韩信学学老庄之道，不要称说自己的功劳大，不要夸奖自己的才能高，则他对汉朝的功劳，几乎可以比得上周公、召公、太公，而让后世供奉。”又说：“而天下已集，乃谋叛逆，夷灭宗族（韩信最后被夷灭三族），不亦宜乎？”
司马迁最后这句话，究竟是什么意思，曾经引起过很多争论。其中有一种说法被大多数人所接受，说司马迁这句话的意思是：“既然天下已经要一统了，韩信为什么还要在这种不是造反的时候造起反来？而当他造反以后就灭了他三族，岂是有心肝的人做得出来的？”一方面说韩信，一方面怪高祖及吕后心肠之狠，对这么一位开国大功臣施行那么残酷的刑罚。
另一种说法也有道理，说所谓“天下已集，乃谋叛逆”的“乃”字，是方才的意思。整句话的意思是说：“天下都已经要一统了，才起来造反（不是太慢了吗）。那么，因此而被夷三族，岂不是应该的吗？”
后一种说法可以在这篇列传中找到一处呼应，就是司马迁用了全篇大约十分之一的字数写齐国人蒯通为韩信看相，说：“相君之面，不过封侯，又危（而）不安。相君之背，贵乃不可言。”劝韩信趁早独立，与刘邦、项羽三分天下，然后成就大事。可是韩信“独豫不忍背（叛）汉，又自以为功多，汉终不夺我齐（时韩信为齐王）”。蒯通眼看劝他不动，只好装疯离开了他。最后，韩信被吕后下令斩首时还说：“吾悔不用蒯通之计。”
由这段叙述的大意可见“乃谋叛逆”解释作“到这个时候才起来造反”似乎是前后呼应。这么说来，司马迁是认为韩信太委屈了，他简直可以取代刘邦成为皇帝。当日在刘邦面前拼命推荐韩信的是萧何，而最后参与计划诱杀韩信的也是萧何。所以司马迁不忘记上一笔“吕后欲召，恐其党不就，乃与萧相国谋”。
这个东南游的第一站，司马迁在感慨、叹息中离去。他往南走，到了现在浙江绍兴东南方十三里的会稽山。在没到会稽山之前，他曾经参观了战国时代四大公子之一楚国春申君的故城宫室。
在春申君的时候，楚国的疆域已经扩展到沿海江浙一带，而且它的首都曾设在今安徽寿县。传说黄浦江就是春申君开凿的，今上海附近就是他的封邑，上海北门外有“春申君祠”，上海的简称“申”和春申君有很大的关系。照司马迁的路线来看，他参观的春申君的故城宫室，大概就在现在的上海一带。他赞叹地记道：“盛矣哉！”可见他去的时候，那个故城还依然存在。
在会稽山，他首先去看了“禹穴”，这是一个山洞，据说大禹曾经进去过。而会稽山是当年大禹会见天下诸侯的地方，山上有禹王庙，山下有大禹陵墓。又据说会稽山原名茅山，是大禹改的名字，理由是他会诸侯在此地计算各国的赋税，而会稽就是“会计”。
除了大禹会诸侯以外，大禹的后代越王勾践也曾在这里卧薪尝胆。司马迁的《越王勾践世家》可能也是将在这里听到的一些流传中的故事作为材料。
至于会稽山的北面太湖一带，当年吴王夫差的故地，司马迁也可能前去探访过。他回到都城长安后，把那些材料编成春秋末年吴越争霸的文字。