Во время посещения Нидерландов в июне 1933 он открывает для себя фламандскую живопись и уже в октябре поступает в Бельгийскую Королевскую Академию наук и искусств, где посещает курсы античного рисунка Анри ван Хаалена. Николя подружился с Мадлен Опер – выпускницей знаменитого «Парижского изобразительного искусства», именно она познакомила его с абстрактной живописью. В Академии изобразительных искусств Сен-Жиль-де-Брюссель он занимается архитектурой у Шарля Малькоза, здесь же в 1934-1935 годах он обучается искусству декорирования у Жоржа де Вламинка, благодаря чему участвует в создании росписей павильона сельского хозяйства на Всемирной выставке в Брюсселе в 1935 году.

Затем Николя путешествует по всей Европе. В Париже он знакомится с Полем Сезанном, Анри Матиссом, Хаимом Сутиным, Жоржем Браком. После Франции – Испания, он путешествует на велосипеде, наслаждаясь великолепными пейзажами, делает много набросков. Из Мадрида вместе с Эммануэлем Д’Хогворстом Николя едет в Андалузию. Здесь он пишет несколько акварелей, которые успешно продает в Барселоне. В 1936 году в брюссельской галерее Дитриха он выставит другие акварели, выполненные в Испании в галерее Дитриха, одновременно с ним выставляется Ростислав Лукин.

В 1937 году в Марракеше, куда Николя де Сталь отправляется в поисках сюжетов для своих картин, он встретился с художницей Жаннин Гийю. Жаннин старше Николя на 5 лет и, к тому же, она уже 6 лет замужем за польским художником Олеком Тесларом, с которым она познакомилась в Высшей национальной школе декоративного искусства в Ницце, имеет сына, Антека, который впоследствии станет писателем и сценаристом под псевдонимом Антуан Тюдаль. Жаннин уезжает с Николя, Теслар не препятствует ее отъезду.

Жаннин, обучавшаяся в Ницце декоративному искусству, уже утвердилась, как художник, а Николя по=прежнему ищет свой стиль. Николя, по-прежнему ищет свой стиль. Он вдруг стремится в Италию. В 1938 году он вместе с Жаннин он посещает Неаполь, Помпеи, Фраскати, Пестум, Сорренто, Капри.

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

Чтобы заработать немного денег, он возвращается в Бельгию. В Льеже он работает над фресками выставочного павильона Франции для Международной выставки водной техники.

В сентябре 1939 года художник поступил в Иностранный легион. За два месяца до этого Николя знакомится с галеристкой Жанной Бюше, которая находит для него и для Жаннин временное жилье в незанятых мастерских художников.

19 января 1940 года его призывают в армию и направляют в Алжир, а затем в Тунис. Но уже 19 сентября 1940 Николя демобилизован и едет в Ниццу, где уже проживает Жаннин. Там он знакомится с Альберто Маньелли, Марией Еленой Виейра да Сильва, Жаном Арпом, Кристин Бурместер, Соней и Робертом Делоне. Художники встречаются в книжном магазине Матарассо с Жаком Превером и Франсуа Карко. Именно благодаря своему другу, живописцу Феликсу Обле, он будет введен в эти художественные круги и направит свою живопись в более абстрактный стиль. Обле приходит ему на помощь, когда молодой художник не может зарабатывать на жизнь своей живописью, предоставляя ему небольшие заказы на декорирование помещений.