13 марта 1833 года решением фонда средства для заграничной поездки в размере 1200 ригсдалеров на срок два года Андерсену были выделены. Впоследствии, 15 апреля 1834 года, по прошению Йонаса Коллина к этой сумме были добавлены еще 200 ригсдалеров. Вскоре Андерсен передал неоконченные автобиографические записки на хранение Эдварду Коллину и 22 апреля отбыл из Копенгагена, направляясь через Германию в Париж и далее — в Италию.

Без особых приключений Андерсен всего за неделю проехал через Германию. В Гамбурге он посетил немецкого композитора и скрипача, автора нескольких сказочно-романтических опер Людвига Шпора, а во Франкфурте побывал из любопытства в мрачном, но чистом еврейском гетто, где, отказываясь от более роскошной обстановки, проживала мать миллионеров Ротшильдов. Впечатления от гетто пригодились писателю впоследствии — при работе над первым романом, о котором речь еще впереди.

В Париж Андерсен приехал очень усталым и, остановившись в гостинице, тут же лег спать, но был разбужен, как ему показалось, орудийными залпами, вспышками яркого света и гомоном толпы. Спросонья он подумал, что во Франции опять произошла революция, однако, выглянув в окно, убедился, что всего-навсего в театре напротив закончился водевиль и к тому же на улице гроза.

Андерсен пробыл во Франции чуть больше трех месяцев. Он посетил главные исторические достопримечательности Парижа, Трианон в Версале, а в нем — комнату Наполеона, героя, снившегося башмачнику Андерсену в его предсмертном кошмаре. В июле Ханс Кристиан сам стал участником и зрителем трехдневного празднества в честь французской революции 1830 года и видел, как в торжественной обстановке открывалась на Вандомской площади колонна, воздвигнутая в честь Наполеона I.

Как ни странно, но в Париже Андерсена стало угнетать чувство одиночества. Возможно, одной из причин того было его неважное владение французским. Кроме того, он более месяца ни от Эдварда Коллина, к постоянному общению с которым, по-видимому, привык, ни от других друзей не получил ни одного письма. Коллину было в то время не до переписки, только что состоялась его помолвка с Хенриеттой Тюберг.

Зато Андерсен получил письмо от врага. На его имя пришла довольно пухлая заказная (и неоплаченная) бандероль, в которой получатель нашел странное отправление — номер газеты «Копенгагенская почта» с напечатанным в нем стихотворным пасквилем под заглавием «Прощай, Андерсен». Вот начальная строфа из него:

Андерсен так никогда и не узнал, кто был автором этих строк. Возможно ли, что это был кто-то из тех людей, с которыми он дружил? «Увы, злость настолько распространена, что невольно ею заражаешься», — писал он с связи с этой зародившейся у него мыслью в «Моей жизни как сказке без вымысла».

Но, даже плохо владея французским языком, датский поэт завязал в Париже несколько интересных знакомств. Он посетил Виктора Гюго, находившегося тогда в зените своей славы (портрет писателя висел на стене комнаты Хенриетты Вульф-младшей). У Андерсена не было к нему рекомендательного письма, но он все же попросил, чтобы его приняли, сославшись на то, что завтра покидает Францию. Гюго встретил его в халате и домашних туфлях и оставил автограф в андерсеновском альбоме, который датский поэт держал для подобных случаев.

Кроме того, совсем к тому не стремясь, он познакомился и с прославленным Генрихом Гейне, поэзию которого знал и любил. Гейне сам зашел к Андерсену в гостиницу и оставил портье свою визитную карточку, однако датчанин на нее не отреагировал: близкого общения с «человеком, которого следовало опасаться особенно», как писал он в послании Кристиану Войту от 26 июня 1833 года, он не желал. Что было тому причиной: язвительность Гейне или его политический радикализм, так и осталось неизвестным. Впрочем, через три недели, когда Андерсен гулял по бульвару, кто-то хлопнул его по плечу, и этим человеком был Гейне. Они долго говорили о литературе. Немецкий поэт живо интересовался скандинавской литературой и творчеством Эленшлегера, считая его одним из лучших современных поэтов Европы. Перед отъездом из Парижа Андерсен нанес Гейне прощальный визит, и тот сделал дружескую запись в его альбоме.

Жажда творчества не оставила Ханса Кристиана и в суматошной атмосфере Парижа. Он решил написать на сюжет датской народной баллады «Агнете и Водяной» драматическую поэму и настолько увлекся замыслом, что уверовал — именно этим своим произведением, воплощавшим, как ему тогда казалось, дух датского народа и датской природы, он завоюет окончательное признание на родине. Пересказ незамысловатого сюжета баллады лучше всего предоставить самому автору:

Андерсен задумал написать поэму в двух частях и первую начал и закончил еще в Париже, а вторую написал в горном Ле Локле, маленьком городке, располагавшемся на уровне альпийских лугов во французской Швейцарии в кантоне Ури. Здесь его приютил у себя в доме по рекомендации Урбана Йоргенсена (дом его матери Анны Лет Йоргенсен Андерсен довольно часто посещал в Копенгагене) его зять и часовых дел мастер Жюль Урье, с которым Ханс Кристиан лично познакомился в Париже. Первоначально он, следуя совету Эдварда Коллина, хотел отправиться в Швейцарию для изучения французского языка: в Париже Андерсен вынужденно общался, как тогда было принято, в основном со своими соплеменниками. Однако, приехав в Ле Локль, он понял, что почти не понимает местного французского говора. Зато пребывание в Ле Локле послужило отличной творческой командировкой.