Впечатление от этой постановки было настолько сильным, что певческая академия решила теперь включать в свой репертуар «Страсти по Матфею» каждый год. Этим молодой Мендельсон дал решительный импульс к возрождению Баха в XIX веке, а сам получил международное признание. Этот концерт принес молодому музыканту настоящий триумф.
Через несколько недель он впервые посетил Англию, где приобрел множество друзей и выступил весьма успешно как на музыкальном, так и на общественном поприще. Путешествие началось с Лондона, который, так же, как когда-то Гайдна, поразил его величиной и шумом: «Это ужасно! Это безумно!.. Лондон — самое грандиозное, самое невероятное чудовище на свете!» Мендельсон побывал также в Шотландии и в Уэльсе. Поездка в Шотландию дала ему много незабываемых впечатлений; своеобразная северная природа, полная суровой красоты, возбудила творческое воображение композитора. Шотландия потрясла его дикой природой, странными обычаями и туманными историческими воспоминаниями. Во время этого путешествия самым ярким впечатлением были Гебридские острова и чудо природы — «Фингалова пещера» на одном из них. Так возникли первые наброски концертной увертюры «Гебриды» («Фингалова пещера») и симфонии, впоследствии названной «Шотландской». Спустя 35 лет Брамс скажет о «Гебридах»: «Я отдал бы все свои сочинения, если бы мне только удалась такая вещь, как «Гебриды».
В конце 1829 года он вернулся на родину и очень быстро написал свою первую зрелую симфонию — «Реформационную», которой он откликнулся на 300-летие Реформации — утверждение лютеранства в Германии. Мы должны понимать, как велико ее значение в истории развития жанра — это первая программная романтическая симфония. Ведь хотя все творения Шуберта уже были написаны, они продолжали пылиться в архивах брата и друзей, и лишь через 10 лет тот же Мендельсон исполнит 9-ю симфонию Шуберта. А «Фантастическая» симфония Берлиоза будет написана через несколько месяцев после «Реформационной».
Вскоре Мендельсон возобновил странствия. В мае 1830 года композитор смог отправиться в большое путешествие по Европе: Мюнхен, Париж, Зальцбург, Вена, Венеция, Флоренция, Рим, Швейцария. Прибыв в Мюнхен, он почувствовал себя «по-домашнему уютно», его сердце пылало любовью к красивой Дельфине фон Шаурот. Ей он посвятил свой клавирный концерт, который быстро написал на бумаге и исполнил в присутствии баварского короля. Мендельсон отправляется в Париж: добивается успеха как пианист, но не как композитор. В Риме он встретился с Берлиозом и начал работу над двумя симфониями — Четвертой ля мажор («Итальянской», 1833) и Третьей ля минор («Шотландской», 1842); в 1832 году снова побывал в Париже, где приобрел новых друзей (среди них — Шопен). Если его увертюра «Сон в летнюю ночь» имела небольшой успех, то с «Реформационной симфонией» было еще хуже. Мендельсон предполагал исполнить ее в Париже. Но французские музыканты высказались о музыке неодобрительно: «Слишком много фугато и слишком мало мелодий».