Путешествуя с женой по Швейцарии и Северной Италии, Хейденстам с головой погружается в мир художественной литературы. С особым вниманием он читает произведения Стриндберга. «Красная комната» оставляет его равнодушным, но «Браки» приводят в восторг, и он отправляет Стриндбергу приветственное письмо, поздравляя с творческой удачей. В 1885 г. в Швейцарии происходит их личная встреча, а потом они вместе направляются в Рим. Как поведан Хейденстам в книге путевых заметок о Швейцарии «От Коль ди Тенда до Блоксберга» (1889), во время долгих бесед со Стриндбергом они обмениваются мнениями о проблемах современной жизни, культуры, литературного творчества. Горестное чувство невосполнимой утраты рождает у Хейденстама разрушение старой дворянской культуры, искони укоренившихся устоев и традиций под напором бездуховности и прагматизма нарождающейся буржуазии. «Ты принадлежишь к новому дворянству, дворянству нервов… Я — к старому, дворянству мускулов… Мы вымираем, уступая место дворянству денег…». По мнению критика Г. Линдблада, эти слова Хейденстама навеяли Стриндбергу замысел драмы «Фрёкен Жюли». Но они важны еще и тем, что многое объясняют в мировоззрении самого Хейденстама, стремившегося, как позднее и сам Стриндберг, существующей системе ценностей противопоставить альтернативный мир. И хотя вскоре из-за несходства литературных позиций их пути расходятся, Хейденстам по-прежнему высоко ценит Стриндберга, считая его первым среди шведских писателей. В день 50-летия Стриндберга 22 января 1899 г. он публикует в его честь стихотворение «Августу Стриндбергу», в котором создает проникновенный образ одинокого и гордого художника, умеющего говорить горькую, нелицеприятную правду, непонятого и оскорбленного.
Весной 1887 г. Хейденстам из Швейцарии возвращается на родину, получив известие о смертельной болезни отца, а после его смерти обосновывается в Ольсхаммере. Здесь, в старом поместье, он готовит к изданию свой первый поэтический сборник «Паломничество и годы странствий».
Этот сборник увидел свет в 1888 г. и получил одобрение ведущих шведских поэтов В. Рюдберга и К. Снойльского, подтвердивших, по сути, то, что еще раньше сказал о Хейденстаме прочитавший в рукописи его юношеские стихи Топелиус: «В Швеции родился новый замечательный поэт». По признанию Хейденстама, он долго не решался напечатать свои стихи, так как «дух его, в котором, словно на поле брани, сражались натурализм и романтизм, пребывал в смятении». И только «пережив свой период «бури и натиска» и убедившись в правильности выбранного пути, он был готов к тому, чтобы публично заявить о своих литературных взглядах.
В «Паломничестве и годах странствий» впервые в шведской литературе воплощен эстетический идеал неоромантизма. Хейденстам воспевает прекрасный, чарующий, «первобытный» Восток как альтернативу современной западной цивилизации. Этот сказочный мир красоты, любви и жизнерадостности — высшая форма человеческого существования, убежище от пошлой и меркантильной действительности. Стихи сборника пленяют читателя прелестью импрессионистических зарисовок, основанных на мимолетных впечатлениях от увиденного, и в то же время словно рожденных неудержимой фантазией поэта. По выражению рецензировавшего сборник Левертина, «этот Восток при всей своей натуральности более всего походит на сказки из «Тысячи и одной ночи». В наполненных чувствами пейзажах, в изображении красочных подробностей бытия поэт не устает прославлять радость жизни, безграничную силу любви.
Однако на фоне светлых картин часто возникают грустные, меланхолические тона. Поэта мучит мысль о том, что этот прекрасный и радостный мир обречен. Дух прагматизма, наживы, голого расчета проникает и сюда, в еще не испорченный цивилизацией, древний Восток, к которому он привязан самым горячим чувством любви.
Романтическим неприятием действительности проникнут и, автобиографический в своей основе, образ лирического героя, одинокого бунтаря, который не боится смерти и бросает вызов Богу, восстает против людских законов и тоскует по красоте и величию давно минувшего.
С выходом в свет «Паломничества и годов странствий» начался новый этап в развитии шведской литературы: натурализм с его ориентированностью на иллюзию правдоподобия уступил место искусству, возрождавшему традиции романтизма. Борьбу за утверждение идеалов нового искусства, открывающего простор выражению творческой индивидуальности художника, Хейденстам повел сознательно и целеустремленно.