Первый небольшой сборник сказок Андерсена вышел весной 1835 года. Ко времени выхода романа «Всего лишь скрипач» Андерсен уже напечатал три первых выпуска «Сказок, рассказанных детям», в которые, помимо прочих, вошли такие прославленные впоследствии произведения, как «Огниво» и «Принцесса на горошине» (1-й выпуск. 1835 год), «Дюймовочка» и «Дорожный товарищ» (2-й выпуск.1836 год), «Русалочка» и «Новое платье короля» (3-й выпуск. 1837 год). Если критика в целом одобрительна приняла романы Андерсена, то к сказкам она отнеслась довольно скептически. Утверждалось, что они слишком детские для взрослых и недостаточно поучительны и назидательны для детей, не говоря о том, что язык в отношении правильности оставляет желать лучшего. И уж совсем плохо обстояло дело с пьесами. Из шести предложенных пять были отвергнуты как безнадежно наивные и дилетантские.
Печаль и горечь поэта из-за этих литературных невзгод тем более росли, что его книги прекрасно принимали в Германии. «Импровизатор» вышел на немецком языке еще в 1835 году, «О.Т.» — в 1837, «Только скрипач» — в 1838, и все вызвали безраздельный восторг. Брауншвейгский издатель даже попросил его написать небольшой автобиографический очерк, который был напечатан в виде предисловия к немецкому переводу «Скрипача». Поэту оставалось лишь думать, что на родине, в Дании, он был жертвой грубого личного преследования.
Андерсен твердо решил победить критику и завоевать театр. Зимой 1839 года он написал большую пятиактную драму «Мулат», действие которой разворачивается в Becт-Индии; сюжет он позаимствовал из одной французской новеллы. Пьеса была принята к постановке, фру Хейберг получила одну из главных ролей, и успех казался обеспеченным. Однако премьеру постановки, назначенную на 3 декабря, отменили из-за смерти Фредерика VI. Это было жестокое потрясение. Все соболезновали несчастному Андерсену, который утешался только тем, что к рождеству в книжных лавках появилось его новое произведение «Книга картин без картин», а под Новый год вышла третьим изданием «Прогулка на Амагер». Премьера «Мулата» состоялась только 3 февраля 1840 года, когда снова открылся театр. И тут Андерсен был вознагражден. Пьеса имела большой успех. Андерсена переполняла радость и благодарность к богу.
Однако недоброжелатели тут же обратили внимание на то, что пьеса не оригинальна: ведь он позаимствовал сюжет из французской новеллы. Этого оказалось достаточно, чтобы уязвленный поэт начал писать новую большую драму, целиком и полностью собственного сочинения — этим он бы заставил умолкнуть чересчур рьяных критиков. В пьесе шла речь о борьбе испанцев против мавров во времена средневековья, и по главной героине она получила название «Мавританка». За лето он закончил ее и отдал в театр. К сожалению, новая пьеса принесла одни огорчения. Дирекция очень нерешительно принимала ее, а когда наконец приняла, то начались проволочки с постановкой. Сначала на очереди стояли другие пьесы, фру Хейберг отказалась от роли, которую Андерсен написал специально для нее, Хартман не успевал закончить музыку, театр опаздывал с премьерой. Осень кончилась, постепенно автора обуяло патологическое нетерпение, ему повсюду мерещились козни недругов и насмешки, и, наконец, ожесточившись и отчаявшись, он решил уехать за границу. Не дожидаясь откладываемой со дня на день премьеры, он собрал остатки своих сбережений и в конце октября отбыл в Германию, а потом дальше, в Италию.
Он совершенно потерял самообладание, был в нервном и расстроенном состоянии после вынужденной изнурительной работы над «Мавританкой» и неприятностей с театром; даже приехав в Италию месяц спустя, он еще был далеко не здоров. На него сыпались все новые несчастья. Свидание с Римом принесло большое разочарование. Зима 1840/41 года была необычно холодной и дождливой, он мерз и страдал от простуд и зубной боли, потом получил известие, что «Мавританка» провалилась и была снята после трех представлений. Как будто этого было мало, он далее услышал, что Хейберг издал сатирическую книгу, где выставил его шутом. Речь шла о «Душе после смерти». Андерсен сильно расстроился. Февральский карнавал немного развеселил его, а первого марта в Неаполе он получил 600 риксдалеров королевской стипендии на дорожные расходы, и теперь он наконец мог осуществить свою мечту попасть в Грецию и Константинополь, и ожидание увидеть нечто совершенно новое вернуло его к жизни.
14 марта 1840 года он поднялся на борт французского судна, идущего на восток. Они плыли через Мальту и Сирое в Пирей и 24 марта прибыли в Афины. Немецкие газеты уже объявили о его прибытии, и маленькая колония немцев и датчан сделала все, чтобы он чувствовал себя хорошо и с пользой провел время. Его представили ко двору, и он неоднократно был гостем королевской четы. Он как бы получал возмещение за страдания в Копенгагене. В Греции он пробыл месяц, затем отправился в Константинополь. По дороге ему представилась возможность сойти на берег в Смирне и впервые в жизни увидеть землю Азии; на узких улицах ему встречались верблюды и страусы, в давке он вынужден был «протискиваться среди евреев, греков и турок! Что это был за маскарад!» — писал он на родину. В Константинополе он провел десять дней, за это время осмотрел Софийскую мечеть, посетил базары и кладбище в Скутари на другой стороне Босфора, присутствовал на сеансе у завывающих дервишей и прочитал на немецком языке несколько своих сказок на вечере у австрийского посланника.
Он собирался возвращаться домой по Дунаю через Вену. В то время в турецких владениях на Дунае произошло восстание, и все советовали ему выбрать путь через Грецию и Триест. После долгих размышлений он все же решил пойти на риск. «Желание увидеть что-то новое так велико, — писал он, — что побеждает страх. Я еду. Есть же в мире Бог!» Плавание было немного беспокойное, но все же он благополучно прибыл в Вену и вернулся в Копенгаген летом 1841 года.
Второй раз в жизни путешествие за границу спасло его от копенгагенских разочарований и огорчений и привело в состояние гармонии с самим собой и с окружающим миром. Больной и подавленный, покидал он Данию, домой вернулся воодушевленный и здоровый. Он пережил много нового и интересного: впервые ездил по железной дороге в Германии, плавал по Средиземному морю в шторм и штиль, ступил на землю Греции и вблизи видел Восток. Он собрал материал для новой книги, которая полностью заняла его мысли на ближайшее время. Воля к жизни снова наполняла его. Строчки Хейберга о нем в «Душе после смерти теперь казались ему невинными и безвредными. Опубликовав через год после возвращения на родину «Базар поэта» — книгу о своем большом путешествии, он без всякой горечи мог радоваться ее успеху у читателей и принимать кислые и педантичные замечания критики со снисходительностью космополита.
Путешествием в Грецию и на Балканы начался новый значительный отрезок в жизни поэта, эпоха, которая принесла ему самые триумфальные победы, самые большие личные разочарования, самые крупные национальные события, самые высокие художественные достижения. Сороковые годы стали кульминацией его жизни. Именно в эти годы исполнилась его мечта о всемирной известности, причем в таких масштабах, что ему приходилось, как Иеппе, щипать себя за руку и спрашивать, неужели и вправду он, мальчик из бедной семьи, достиг таких вершин.