Отец Николая, Владимир Иванович Сталь фон Гольштейн, окончил Ставропольское казачье юнкерское училище, сделал успешную военную карьеру. В 1908 году он стал генерал-майором, помощником коменданта Петропавловской крепости. В апреле 1917 году уволен со службы в связи с болезнью. Его мать, Любовь Владимировна, в девичестве Березникова, была моложе мужа на двадцать два года. Она происходила из творческого семейства, где интересовалась искусством; по матери она была родственницей композитора Александра Глазунова.
После революции 1917 года, как и многие дворянские семьи, фон Гольштейны были вынуждены покинуть Россию. Не сумев выехать в Эстонию, семья с большим трудом добралась по Вильно, который тогда принадлежал Польше. Здесь жила подруга матери Николая, его крестная, которая помогла им обустроиться. В 1921 году скончался Владимир Иванович, а через год за ним последовала Любовь Владимировна. Трое детей — Николай и его сестры Марина и Ольга остались сиротами. Крестная не бросила детей, а постаралась найти им приемную семью. И ей это удалось — детей усыновила семья Фрисеро из Брюсселя. Корни их рода были в Сардинии, но еще в XIX веке отец Эммануэля Фрисеро получил российское подданство, когда служил военно-морским атташе при Русском посольстве в Лондоне. Его жена Шарлотта — была президентом Красного Креста.
16 августа 1924 года Николя де Сталь (так теперь на французский манер звучало его имя) поступил в иезуитский колледж Святого Михаила в Эттербеке, соседней с Брюсселем коммуне, в предпоследний класс начальной школы. В сентябре 1931 года Николя поступает в колледж Кардинала Мерсье в Брэн-л’Аллё. Он увлекается французской литературой и греческими трагедиями и в то же время открывает для себя мир живописи: в музеях и галереях он часами рассматривает картины Рубенса и современных бельгийских художников Джеймса Энсора, Константа Пермеке. Его зарождающаяся склонность к профессиональному занятию живописью беспокоит приемного отца, Эммануэля Фрисеро: он сам был выпускником Центральной высшей школы Парижа — высшего учебного заведения, готовящего инженеров в области науки и машиностроения. Поэтому он хочет, чтобы Николя переключился на науку и побудил его получить инженерное образование. Но по окончании учебы Николя обращается к живописи.
Во время посещения Нидерландов в июне 1933 он открывает для себя фламандскую живопись и уже в октябре поступает в Бельгийскую Королевскую Академию наук и искусств, где посещает курсы античного рисунка Анри ван Хаалена. Николя подружился с Мадлен Опер — выпускницей знаменитого «Парижского изобразительного искусства», именно она познакомила его с абстрактной живописью. В Академии изобразительных искусств Сен-Жиль-де-Брюссель он занимается архитектурой у Шарля Малькоза, здесь же в 1934–1935 годах он обучается искусству декорирования у Жоржа де Вламинка, благодаря чему участвует в создании росписей павильона сельского хозяйства на Всемирной выставке в Брюсселе в 1935 году.
Затем Николя путешествует по всей Европе. В Париже он знакомится с Полем Сезанном, Анри Матиссом, Хаимом Сутиным, Жоржем Браком. После Франции — Испания, он путешествует на велосипеде, наслаждаясь великолепными пейзажами, делает много набросков. Из Мадрида вместе с Эммануэлем Д’Хогворстом Николя едет в Андалузию. Здесь он пишет несколько акварелей, которые успешно продает в Барселоне. В 1936 году в брюссельской галерее Дитриха он выставит другие акварели, выполненные в Испании в галерее Дитриха, одновременно с ним выставляется Ростислав Лукин.
В 1937 году в Марракеше, куда Николя де Сталь отправляется в поисках сюжетов для своих картин, он встретился с художницей Жаннин Гийю. Жаннин старше Николя на 5 лет и, к тому же, она уже 6 лет замужем за польским художником Олеком Тесларом, с которым она познакомилась в Высшей национальной школе декоративного искусства в Ницце, имеет сына, Антека, который впоследствии станет писателем и сценаристом под псевдонимом Антуан Тюдаль. Жаннин уезжает с Николя, Теслар не препятствует ее отъезду.
Жаннин, обучавшаяся в Ницце декоративному искусству, уже утвердилась, как художник, а Николя по=прежнему ищет свой стиль. Николя, по-прежнему ищет свой стиль. Он вдруг стремится в Италию. В 1938 году он вместе с Жаннин он посещает Неаполь, Помпеи, Фраскати, Пестум, Сорренто, Капри.
Между тем, отношения с Фрисеро ухудшаются: приемная семья обеспокоена карьерой Николя, который разрывает все связи с Бельгией и решает обосноваться с Жаннин в Париже. Некоторое время он посещает курсы Академии Фернана Леже и пытается получить вид на жительство, копируя работы в Лувре. Николя знакомится с швейцарским искусствоведом Пьером Куртионом, который впоследствии будет играть важную роль в его жизни. В течение этого года Николя очень много рисует и уничтожает многие из своих произведений. От этого периода остался лишь «Вид на набережные Сены».