След една безсънна нощ Андерсен отива при австрийския консул в Цариград и го моли за съвет. Консулът му обяснява, че особен риск за пътуване през България няма, още повече, че по същия път ще заминат за Виена двама австрийски офицери, към които той може да се присъедини. Успокоен от думите на консула, Андерсен най-сетне решава да мине по Черно море и Дунава. В автобиографията си „Приказка на моя живот“ ето как той описва това свое пътуване:

Статуята на Малката русалка в Копенгахен (Дания)
На четвърти май вечерта аз седнах на парахода и ние заплувахме по прекрасния Босфор. По пътя имаше и лошо време, и мъгли. Цял ден прекарахме край град Кюстенджа, близо до събореното Траяново укрепление, а след това се затъркаляхме в големи плетени талиги, запрегнали с бели волове, по една пустинна равнина, която минахме за два дена. За безредици в страната чухме едва като стигнахме с парахода при Русчук (Русе).
На другия ден видяхме от парахода покритите със сняг балкани; цялото пространство между тях и нас беше също обхванато от бунт; ние узнахме за това на следната нощ. Един въоръжен татарин, който носел писмо от Видин за Цариград, бил хванат и убит, с друг, изглежда, се случило същото, а трети бе успял да се спаси. Той се беше скрил в крайдунавската тръстика и дочака нашия параход. Видът на тоя човек, в дреха от кожи с обърната навън козина, накичен от главата до петите с оръжия, беше просто страшен. Той пътува с нас почти целия ден.
Във Видин слязохме и трябваше да се подложим на силно опушване, понеже там се страхуваха да не внесем чумна зараза от Цариград.
Губернаторът на Видин, Хюсеин паша, ни изпрати последните броеве на „Алгемайне цайтунг“ и ние вече от европейски източник узнахме в какво положение се намират работите на страната. Като минах през Сърбия, Румъния, Унгария и Австрия, аз стигнах най-сетне до Дрезден, отдето по обикновения път потеглих за родината.