高尔基在下诺夫戈罗德又住了两年。在这段时间中，他广泛地结识了各学习小组的青年和“政治家”。
在他们中间，当听他们枯燥而费解的演说时，高尔基觉得自己“就像一只黄雀待在一窝聪明的乌鸦中间一样”。他通过自己的亲身感受，发现这些所谓的“民粹派”只不过是一群脱离人民、脱离现实生活空想主义者。在他们中间，高尔基感到空虚和苦恼。
他想起在喀山和察里津度过的那些日子，他在那里虽然也参加了一些知识分子的集会，碰见过许多优秀的人物，可是即使是他们当中最出色的人，也不免脱离人民，脱离现实社会。他们读书、辩论，但并没有什么行动。高尔基决定，做一次长途旅行去观察真正俄国人民的生活，以自己的亲身经历来了解人民。
1891年4月初的一天，高尔基没有同任何人告别，悄悄地离开了下诺夫戈罗德城。
自从上次被捕放出来以后，高尔基就一直被当地的警察部门秘密监视着。为了避开警察们的“蜘蛛网”，他沿着伏尔加河高高的河岸深一脚浅一脚地艰难跋涉。当他确信没有人跟踪之后，就坐船到了察里津，然后又顺着他所熟悉的察里津横穿过顿河草原。
为了在路途中生活下去，高尔基不时地停下来找些活干，在罗斯托夫港，他在一艘土耳其轮船上每天工作15个小时，装卸潮湿的皮革和一篓一篓的烟叶，一天挣到50戈比。
他住在靠近码头的一座房子的地下室里，在这里，他又结交了不少的码头工人和马车夫。接着，他又漫游到乌克兰。
高尔基从乌克兰的这一村到那一村，发现了许多新奇的事物，当然，也遇到了很多危险。有一次，他几乎淹死在克尔奇海峡；还有一次，在乔其亚公路上，他被封闭在大风雪中。为了生存，他不得不做短暂的停留，挣一点钱，再继续走下一段路。
但是，什么困难也阻挡不了他，因为他要了解俄罗斯。
这年的7月15日，当他经过乌克兰的一个村庄时，碰巧看到了一种当地叫做“马奔”的惨剧。
这是一种残酷的惩罚，是专门施与“不贞节”的女人的。
高尔基看到，一个柔弱的女人，赤身裸体被套在一辆两轮车下，跟一匹马套在一起。一个彪形大汉爬上车，扬起鞭子，一下一下轮流抽打着马和那女人，马车飞快地跑着，车子后面跟着一大群看热闹的人们。在这些村民看来，这不过是例行的风俗，是男人惩罚老婆的平常事而已。
面对这种野蛮、毫无人性地虐待妇女的行为，高尔基挺身而出给以制止。
然而，当地的人们把他殴打了一顿，并把他从村子里拖了出来，扔进灌木丛的污泥中。
傍晚，一位流浪乐师从这里经过，发现了已经不省人事、奄奄一息的高尔基。好心的乐师设法把他送到了当地医院，于是他得救了。
伤愈后的高尔基继续上路了，他下一步行程是到比萨拉比亚。高尔基来到这儿时，正是收获葡萄的季节，于是他又成了收葡萄的工人。
比萨拉比亚风光绮丽的边区使他能得以休息，恢复精力。他穿过比萨拉比亚南部地区，来到了多瑙河畔，之后越过阿克尔曼返回到敖德萨。
高尔基在敖德萨港口当了一阵子搬运工，在这期间，他碰上了一个叫做格鲁吉亚的青年。
格鲁吉亚是个脱离了自己家庭的小少爷，流落他乡之后，他穷困潦倒，看不到使自己摆脱困境的任何出路。出于同情，装卸工高尔基向这位少爷伸出了无私的援助之手，他用自己劳动挣来的钱和食物帮助格鲁吉亚，还陪同他返回家乡。
在他们路过库班的哥萨克村时，高尔基听到迈科普村发生了“牛瘟暴动”的消息。由于沙皇官吏消灭牛瘟不力，当地居民被激怒起来，然而士兵却打死了不少农民。
高尔基连忙带着格鲁吉亚赶到迈科普去，但他的行踪引起了当局的注意，他第二次被逮捕了。
宪兵队长问高尔基为什么来这里，高尔基回答：“我想了解俄罗斯。”
宪兵队长以一副不屑一顾的神情回答高尔基：“这不是俄罗斯，而是猪圈！”
被释放后，高尔基又踏上了漫游的路程。他离开迈科普后先到了别斯兰，然后沿着北高加索山脉向里海走去。
已经是10月底了，高尔基依然同那位格鲁吉亚的富家子弟同路。
他们经过尼古拉耶夫、赫尔松、彼列科普、辛菲罗波尔、雅尔塔、费奥多西亚、刻赤、塔曼、黑海地区和捷尔斯克省，沿着格鲁吉亚于1891年11月来到了高加索的首都梯弗里斯。
当他们到达梯弗里斯之后，那位富家子弟偷走了高尔基的全部东西。虽然他事先曾答应让高尔基住在梯弗里斯自己的家里，但他其实是在欺骗高尔基，并把高尔基抛到了这个陌生的城市中。
因为寒冷和饥饿，高尔基在这里遇到了意外，第三次被捕。
警察局长对他进行了讯问。为了早点离开监狱，高尔基想起了自己曾在察里津铁路局认识的一名朋友亚·纳恰洛夫。
此人在梯弗里斯的一个铁路管理局任职，他很快保释出高尔基后，并利用自己的关系，给高尔基安排了工作。经过长途漫游，高尔基终于在梯弗里斯停下脚来。
高尔基在锻工组干了一个多月后，因为他有些文化，就被调到会计科干起了统计员的工作，专门负责记录统计“机车小修”材料的消耗情况。
纳恰洛夫把高尔基介绍给了他的朋友们，他们大多是梯弗里斯被判刑流放的政治犯。
高尔基在政治犯丹科家里租了一个房间。他在梯弗里斯生活了几乎一年，在这一年的各个季节，他利用假期走遍了高加索。高尔基在此期间收集到使他迷恋的这些地区的各种见闻。
1892年春天，高尔基同自己的朋友机械工人费奥多尔·阿法纳西耶夫到了高加索东部的巴库。
巴库是俄罗斯的石油产地，但是石油工人的痛苦生活和油井老板为追求巨额暴利不择手段的做法，给高尔基留下了深刻的印象。
油田到处是肮脏的井架、管道，钻杆横七竖八杂乱无章地堆在地上、路旁。在沉重、灼热的空气中，飘荡着低沉的、“嘶嘶”的声音。十来个光着脊背的工人拽着一根绳子，在地面上拖着一块很厚的、带有铁链的厚重钢板，他们愁眉苦脸地喊着：“哟哎嗬！哟哎嗬！”
大滴的黑雨点儿落到他们身上。油井喷出很粗的黑柱，柱顶碰到浓厚的、带油的空气，就呈现出蘑菇头的形式；虽然从这个蘑菇头上向下流油，但是它好像在融化着，而体积并不缩小。在这一切里面，有一种可怕的、非现实的或者已经过于现实的、毫无意义的东西存在。
看见这个情景，高尔基的朋友阿法纳西耶夫说道：“我就算是饿死，也决不到这里来干活！”
同年夏天，高尔基又来到了黑海，参加了修筑诺沃罗西斯克公路。这里聚集了数千名遭灾省份的饥民。从表面上看，他们好像是在赈济饥民，而实际上却对饥民进行了极端残酷的剥削。看见他们的遭遇，高尔基感慨万分。
旅行使高尔基增长了许多知识，他更加深入地了解了人民的真实生活，为他后来的文学创作提供了丰富的生活素材。
从黑海回来，高尔基重新回到梯弗里斯，他在当地知识分子和青年工人之间认识了许多人，并同阿法纳西耶夫在新阿尔申纳尔街一间半地下室组织了一个学习小组。
高尔基和具有革命思想的工人和学生们有了接触。他在青年学生和工人积极分子中间进行宣传，他变成了小组中的宣传家，他的讲话的天才使新朋友们大为吃惊。
在这个阶段，高尔基认识了一个对他有决定性影响的人，这就是革命者秘密组织“民主党”的会员亚历山大·梅地福维奇·卡柳日内。
亚历山大·梅地福维奇·卡柳日内也是铁路局里的一个职员。由于他参加民意党的革命活动，曾坐过6年牢。他极有知人之明，他与高尔基结识后，发现了高尔基是个与众不同的青年。高尔基不仅阅读过众多的文学名著，还极其看重精神生活，喜欢对社会现象进行各种思索，卡柳日内很是欣赏他。
卡柳日内请高尔基到他家里去住。高尔基在漫长的晚上，对他的新朋友叙述了他的流浪生活中的全部遭遇，讲了他在铁路的冒险故事，也说到了自己的感受。
有一次，高尔基向卡柳日内谈到他在比萨拉比的流浪生活时，在吉普赛人的帐篷里，听到一个名叫马卡尔·楚德拉的老吉普赛人讲的关于拉达和左巴尔的传说。
从高尔基绘声绘色的讲述中，卡柳日内看出高尔基具有非凡的才能，他认为对方是一个真正的文学天才。
卡柳日内把高尔基锁在自己的屋里，拿给他一支笔说：“彼什科夫先生，你把你说给我听的故事写下来吧！”
高尔基吃惊地望着卡柳日内，一时没有反应过来。
卡柳日内从房间里拿出一叠纸，接着说：“给你，纸。你要是不写好，我就不放你出去！”
对于写作这件事，高尔基从来不觉得困难，但是，他到底该写些什么呢，他的大脑里又反复地思索了一遍。
到现在为止，高尔基已经积累了很丰富的素材，漫游生活使他接近了各色各样的人物：在房屋地下室住的人，在作坊和轮船房舱里住的人，在农民的木头小屋和安适整洁的都市建筑里住的人，以及住茅草屋的人。他知道做一个捡垃圾的、当厨子的、画圣像的、做面包师傅的、码头工人、肩挑小贩和铁路工人都是什么滋味。
高尔基想，只要写下来，写自己，写自己亲眼所见的一切，写自己的感想，就行了。然而高尔基一提起笔，这一切的丰富素材就好像从他的记忆中消退了。他另外地写了一些字句，不是他自己的话而是模仿了英国诗人拜伦的诗，或者是那个意大利诗人莱奥巴尔弟的诗文。
卡柳日内当然不希望看见高尔基的这些诗文，他想要看到的是高尔基以自己的经历写成的小说故事。
但卡柳日内也明白这其中的缘故，于是他再次鼓励高尔基说：“你应当把你看见的以故事的方式写出来，而不是以诗歌的方式表达。”
在这种情况下，高尔基重新将自己的诗歌修改成了一篇小说，他的第一篇小说《马卡尔·楚德拉》就此诞生。
卡柳日内把这部小说介绍给梯弗里斯的一家重要的报纸《高加索报》的编辑看，这篇小说立即引起了报社的极大兴趣。
高尔基被报社请进了报馆，报馆编辑部希望他提供一个小说的署名。他坐在编辑部，当场想出一个笔名：马克西姆·高尔基。
马克西姆是他父亲的名字，而“高尔基”在俄文中的意思是“最大的痛苦”。高尔基觉得，幸福往往孕育在痛苦之中，希望也是诞生在痛苦之中，所以他便以这个名字为命。谁也没有想到，这个名字后来竟震动了整个俄国和世界文坛。
1892年9月24日，《高加索报》发表了署名为“马克西姆·高尔基”的小说《马卡尔·楚德拉》。这件事对于高尔基的意义非同小可：喜爱文学的青年高尔基破天荒地在报刊上发表了自己的第一篇作品，在文坛上迈出了坚实的第一步，这是他整个创作道路的开端。
后来，高尔基一直怀念他开始创作活动的城市梯弗里斯，念念不忘帮助他的卡柳日内。1925年，57岁的高尔基在致卡柳日内的信中写道：
我亲爱的朋友和老师，亚历山大·梅地福维奇·卡柳日内：
自从我有幸同您相识以来，已经过去了34年了；而从我们第二次也就是最后一次见面以来，也过去了22年了。
在此期间，我结识过数百人，他们之中有的是了不起的、卓越的人物。可是，请您相信：他们之中的任何人在我的记忆里与您相比都会黯然失色。
这是因为，亲爱的朋友，您是第一个像对待人一样对待我的人。
在我的记忆里，您第一个用您那温柔的使我永不能忘怀的目光看我，您不光是把我看做一个有奇怪经历的小伙子和漫无目的的流浪汉，而且还把我看做一种有用的、能够创造社会财富的人。当您在倾听我讲述我的所见所闻和我自己本人的经历时，我记住了您的眼睛。
