Весной 1887 г. Хейденстам из Швейцарии возвращается на родину, получив известие о смертельной болезни отца, а после его смерти обосновывается в Ольсхаммере. Здесь, в старом поместье, он готовит к изданию свой первый поэтический сборник «Паломничество и годы странствий».
Этот сборник увидел свет в 1888 г. и получил одобрение ведущих шведских поэтов В. Рюдберга и К. Снойльского, подтвердивших, по сути, то, что еще раньше сказал о Хейденстаме прочитавший в рукописи его юношеские стихи Топелиус: «В Швеции родился новый замечательный поэт». По признанию Хейденстама, он долго не решался напечатать свои стихи, так как «дух его, в котором, словно на поле брани, сражались натурализм и романтизм, пребывал в смятении». И только «пережив свой период «бури и натиска» и убедившись в правильности выбранного пути, он был готов к тому, чтобы публично заявить о своих литературных взглядах.
В «Паломничестве и годах странствий» впервые в шведской литературе воплощен эстетический идеал неоромантизма. Хейденстам воспевает прекрасный, чарующий, «первобытный» Восток как альтернативу современной западной цивилизации. Этот сказочный мир красоты, любви и жизнерадостности — высшая форма человеческого существования, убежище от пошлой и меркантильной действительности. Стихи сборника пленяют читателя прелестью импрессионистических зарисовок, основанных на мимолетных впечатлениях от увиденного, и в то же время словно рожденных неудержимой фантазией поэта. По выражению рецензировавшего сборник Левертина, «этот Восток при всей своей натуральности более всего походит на сказки из «Тысячи и одной ночи». В наполненных чувствами пейзажах, в изображении красочных подробностей бытия поэт не устает прославлять радость жизни, безграничную силу любви.
Однако на фоне светлых картин часто возникают грустные, меланхолические тона. Поэта мучит мысль о том, что этот прекрасный и радостный мир обречен. Дух прагматизма, наживы, голого расчета проникает и сюда, в еще не испорченный цивилизацией, древний Восток, к которому он привязан самым горячим чувством любви.
Романтическим неприятием действительности проникнут и, автобиографический в своей основе, образ лирического героя, одинокого бунтаря, который не боится смерти и бросает вызов Богу, восстает против людских законов и тоскует по красоте и величию давно минувшего.
С выходом в свет «Паломничества и годов странствий» начался новый этап в развитии шведской литературы: натурализм с его ориентированностью на иллюзию правдоподобия уступил место искусству, возрождавшему традиции романтизма. Борьбу за утверждение идеалов нового искусства, открывающего простор выражению творческой индивидуальности художника, Хейденстам повел сознательно и целеустремленно.