После учебы в военных училищах, в 1903 году Николаус стал под знамена имперской армии в качестве фенриха и в 1904 году был назначен в 7-й гренадерский полк. Дослужившись до гауптмана, он в 1914 году стал членом Генерального штаба и занимал различные штабные и полковые посты во время первой мировой войны, снискав при этом безупречную репутацию. Он отвечал за операции дивизии «Остзее» генерала графа Рюдигера в Финляндии в конце войны и остался там в составе фрейкора (добровольческого корпуса) до начала 1920 года. По возвращении в Германию Фалькенхорст вступил в рейхсвер и к 1925 году находился в оперативной дивизии Министерства обороны.
С 1933 по 1935 год Фалькенхорст служил военным атташе в Праге, Белграде и Бухаресте, а в 1935 году возглавил штаб группы армий 3 в Дрездене.
Продолжая свое продвижение по карьерной лестнице по мере расширения количественного состава армии, в 1936 году Фалькенхорст стал первым командиром 32-й пехотной дивизии в Кеслине, а в 1939 году был назначен командовать XXI корпусом, сформированным в Алленштейне в Восточной Пруссии. Повышения в чине следовали один за другим: майор — в начале 20-х, оберстлейтенант — 1930 год, генерал-майор -1935, генерал-лейтенант — 1937 год, генерал от инфантерии — 1 октября 1939 года.
Корпус Фалькенхорста сыграл незначительную роль в завоевании Польши и находился в окрестностях Трира в Западной Германии, готовясь к компании против Бельгии и Франции, когда его командующий в феврале 1940 года был вызван в Берлин. Он не знал, что ОКВ занялся планированием операции «Везерюбунг» (вторжение в Норвегию) еще 14 декабря 1939 года. Гитлер не воспринимал этот план всерьез вплоть до 19 февраля 1940 года, когда британский военный корабль вошел в норвежские территориальные воды, захватил в плен немецкое вспомогательное судно «Альтмарк» и освободил около трехсот моряков, захваченных в плен несколькими неделями раньше линкором «Граф Шпее».
Этот инцидент убедил Гитлера в том, что англичане без колебаний посягнут на нейтралитет Норвегии, когда это будет отвечать их интересам. Таким образом, чтобы предупредить высадку британцев в Норвегии и захватить жизненно важные запасы шведской железной руды, которую должны были транспортировать через норвежский порт Нарвик, фюрер решил первым нанести удар. Разные источники утверждают по-разному, кто же именно, Кейтель или Йодль, порекомендовали Фалькенхорста на пост командующего этой операцией, но в данном выборе решающую роль сыграла его служба в Финляндии в 1918 году. Фалькенхорст впервые встретился с Гитлером в рейхсканцелярии 21 февраля и, в отличие от многих других, не был напуган его присутствием. Генерала удивило предложение Гитлера возглавить силы вторжения, включавшие в себя пять пехотных дивизий, но он охотно принял новое назначение. Гитлер велел ему вернуться в 5 часов дня для разработки плана операции.
Поскольку у Фалькенхорста не было ни карты, ни чего-либо другого в этом роде, первым его действием стало посещение книжного магазина, где он приобрел туристический путеводитель «Бедекера». После этого он вернулся в свой гостиничный номер, где решил использовать одну дивизию для захвата главных портовых городов Норвегии — Осло, Ставангера, Бергена, Тронхейма и Нарвика. Хотя концепция Фалькенхорста, естественно, не была проработана столь подробно, как план ОКВ, она все же была очень похожа на него, и Гитлер тотчас же ее одобрил. После этого он снял с поста Фалькенхорста, обратившись к нему с увещеваниями, чтобы тот разработал подробный план и как можно быстрее. Для этой цели ему было разрешено оставить за собой свою собственную штаб-квартиру, которая 1 марта получила более высокий статус и была переименована в XXI группу. Важно отметить, что Браухича (главнокомандующий армией) и Гальдера (начальник Генерального штаба) держали в неведении относительно операции. Оперативный штаб ОКВ действовал в качестве координирующей организации в тех случаях, когда XXI группе нужна была поддержка со стороны прочих служб, а сам Фалькенхорст подчинялся непосредственно Гитлеру.
Когда Фалькенхорст попросил две горнострелковые дивизии, фюрер одобрил просьбу без консультаций с ОКХ.