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