Весной 1887 г. Хейденстам из Швейцарии возвращается на родину, получив известие о смертельной болезни отца, а после его смерти обосновывается в Ольсхаммере. Здесь, в старом поместье, он готовит к изданию свой первый поэтический сборник «Паломничество и годы странствий».
Этот сборник увидел свет в 1888 г. и получил одобрение ведущих шведских поэтов В. Рюдберга и К. Снойльского, подтвердивших, по сути, то, что еще раньше сказал о Хейденстаме прочитавший в рукописи его юношеские стихи Топелиус: «В Швеции родился новый замечательный поэт». По признанию Хейденстама, он долго не решался напечатать свои стихи, так как «дух его, в котором, словно на поле брани, сражались натурализм и романтизм, пребывал в смятении». И только «пережив свой период «бури и натиска» и убедившись в правильности выбранного пути, он был готов к тому, чтобы публично заявить о своих литературных взглядах.
В «Паломничестве и годах странствий» впервые в шведской литературе воплощен эстетический идеал неоромантизма. Хейденстам воспевает прекрасный, чарующий, «первобытный» Восток как альтернативу современной западной цивилизации. Этот сказочный мир красоты, любви и жизнерадостности — высшая форма человеческого существования, убежище от пошлой и меркантильной действительности. Стихи сборника пленяют читателя прелестью импрессионистических зарисовок, основанных на мимолетных впечатлениях от увиденного, и в то же время словно рожденных неудержимой фантазией поэта. По выражению рецензировавшего сборник Левертина, «этот Восток при всей своей натуральности более всего походит на сказки из «Тысячи и одной ночи». В наполненных чувствами пейзажах, в изображении красочных подробностей бытия поэт не устает прославлять радость жизни, безграничную силу любви.
Однако на фоне светлых картин часто возникают грустные, меланхолические тона. Поэта мучит мысль о том, что этот прекрасный и радостный мир обречен. Дух прагматизма, наживы, голого расчета проникает и сюда, в еще не испорченный цивилизацией, древний Восток, к которому он привязан самым горячим чувством любви.
Романтическим неприятием действительности проникнут и, автобиографический в своей основе, образ лирического героя, одинокого бунтаря, который не боится смерти и бросает вызов Богу, восстает против людских законов и тоскует по красоте и величию давно минувшего.
С выходом в свет «Паломничества и годов странствий» начался новый этап в развитии шведской литературы: натурализм с его ориентированностью на иллюзию правдоподобия уступил место искусству, возрождавшему традиции романтизма. Борьбу за утверждение идеалов нового искусства, открывающего простор выражению творческой индивидуальности художника, Хейденстам повел сознательно и целеустремленно.
Свою эстетическую программу он изложил в литературном манифесте «Ренессанс, несколько слов о литературном перевороте», вышедшем в свет в 1889 г. Признавая, что натурализм выразил «здоровый и необходимый» протест против утратившей творческую силу литературы середины XIX в., он тем не менее заявляет, что к началу 1880-х гг. это движение исчерпало свои возможности и уже не в состоянии создать ничего здорового и мощного, кроме «скучной и неинтересной» литературы, которую Хейденстам презрительно называет «реализмом сапожников». Стриндберг, по его мнению, среди шведских натуралистов и реалистов единственный, кто возвышается над массой писателей среднего уровня, ибо ни у кого из них не представлен столь «субъективно выраженный, в соответствии с собственным темпераментом», натурализм, как у него. Главная причина краха натуралистического движения в том, что «узкий догматизм его участников противоречит существу художественного вкуса и ментальности шведской нации, которая чувствует свое духовное родство скорее с Ренессансом, чем с литературными идеалами натурализма 1880-х гг.». В старой шведской литературе, по его мнению, больше смелой фантазии, красочного реализма, экспансивности и богатства жизненных сил, чем в литературе 1880-х. Его мечта — «возродить такую литературу в наши дни». «И если моя мечта оказалась бы не просто мечтой, — пишет он в конце, — если бы это движение действительно возникло и стало развиваться так, как я предполагаю, то какое имя ему следовало бы дать? Разве нельзя его было бы назвать Ренессанс? Оно могло бы претендовать на это название отчасти вследствие особенностей нашего характера, который удостоился бы такой высокой чести, отчасти из-за обращения к средствам и методам старых школ, отчасти также в силу своей природы: склонности к субъективности, художественной самостоятельности, мощи творческой фантазии, смелого реализма и чувства прекрасного». Призыв к созданию субъективного, проникнутого художественной фантазией искусства прозвучит еще раз в написанном совместно с Левертином литературном памфлете «Свадьба Пепиты» (1890), вызвавшем гнев и возмущение Стриндберга. Хейденстам высмеивает здесь безликое изображение унылой повседневности, «бесцветное фотографическое копирование» действительности сторонниками натурализма.
В 1889 г. писатель создает роман «Эндимион» (русск. пер. 1917 г.), который удостаивается восторженной оценки Г. Брандеса, поставившего имя Хейденстама в один ряд с лучшими писателями Швеции. В «Эндимионе» Хейденстам развивает мотив неминуемой гибели еще сохранившихся на Востоке красоты и жизнерадостности под натиском пошлой и бездуховной западной цивилизации. В столкновении Востока и Запада, символически представленных вождем исламского народного движения арабом Эмином и ловким искателем приключений немецким врачом-шарлатаном, исход заранее предрешен. Трагическая гибель Эмина, преданного своими сторонниками, знаменует торжество аморального и циничного Запада над наивным и неиспорченным Востоком.
Однако главное художественное достижение Хейденстама в конце 1880 — начале 1890-х гг. все же не «Эндимион», а также во многом автобиографическое произведение, роман «Ханс Альенус» (1892), работать над которым, по словам Левертина, Хейденстам начал еще в 1887 г. Если «Эндимион» при всей условности сюжета еще крепко связан с традициями реалистического «объективного» повествования 1880-х гг., художественным каноном которого были ранние произведения Стриндберга, то «Ханс Альенус» представляет собой уже нечто иное, с точки зрения новаторства сопоставимое только с «Сагой о Йесте Берлинге» Лагерлёф, торжество ничем не связанной свободной фантазии художника, в форме субъективного лирического монолога утверждающего культ красоты, индивидуализм и гедонизм как альтернативу унылой прозе мещанского существования. Явно ориентированный на образцы европейского символизма, «своей бесформенностью» он вызвал сильное раздражение Г. Брандеса.
Главный герой романа — человек «одинокий и свободный» (таким называет он себя сам), но не испытывающий радости в этом мире. Жизнь словно проходит мимо него. В поисках красоты и счастья он совершает фантастическое путешествие во времени и пространстве (Ватикан, Ассирия, современная Швеция), но жизнь, как и прежде, ускользает от него, и он повсюду чувствует себя чужим — и на карнавале в Риме, и во дворце Сарданапала, и в идиллической атмосфере старинной шведской усадьбы. Его идеал — красота классическая, эллинская, но в нем, как в современном человеке, слишком развита склонность к рефлексии, и приобщение к миру безыскусной красоты и радости ему недоступно. «Недовольство собой — это тяжелейшее бремя, которое суждено нести человеку, — говорит ему римский папа. — Тот, кто чувствует себя не в ладу с собой, остается бездомным до самой смерти».
Мотивы одиночества, тоски, разочарования звучат и во втором поэтическом сборнике Хейденстама «Стихи» (1895). Поэт жалуется на «тесный, душный предел» земной жизни и просит звезды подарить ему «небесный покой». Но в целом сборник знаменует переход к новым поэтическим темам. Подавляющая часть стихотворений посвящена национальному прошлому («Дом», «У гроба с семейными реликвиями», «В ночь на Троицу», «Спящая сестра» и др.). Обращение к истории шведской нации становится для Хейденстама мощным стимулом к духовному обновлению, преодолению декадентских настроений юности. Отрицание упадочнического декадентства и утверждение героического идеала прошлого доминирует в художественной прозе писателя на рубеже XX в.