В двадцать один год Александр Дмитриевич поступил в Николаевскую академию Генерального штаба, главный центр подготовки военной элиты страны. В 1889 году окончил ее по первому разряду (с отличием) и назначен командиром роты Сандомирского полка, затем командиром батальона, старшим адъютантом штаба 4-й пехотной дивизии и штаб-офицером для особых поручений при штабе Кавказского военного округа.
Как офицер Генерального штаба, обученный разведке и контрразведке, Нечволодов подключается к задаче пресечения каналов поступления оружия и взрывчатых веществ из армии к революционным организациям, использующим методы террора. Участвует в предотвращении хищений с военных складов, выявлении каналов контрабанды оружия, финансирования терроризма, который активно распространялся по России.
В 1901 году А. Д. Нечволодова командируют на должность начальника строевого отдела штаба Варшавской крепости с секретной задачей выявления каналов снабжения бомбистов с территории Польши, и он убеждается в могуществе сил, финансирующих тайные организации. Там же, в январе 1902 г. с участием офицеров отделения Штаба округа, военных агентов Генерального штаба и Департамента полиции арестован сотрудник Варшавского штаба округа Гримм, регулярно передававший в Вену и Берлин особо секретные военные документы русской армии, что стало одним из основных аргументов в пользу скорого создания контрразведывательного органа.
В ноябре 1903 года, после создания Разведочного отделения Главного штаба, знаменующего новый этап в деятельности русской военной разведки и контрразведки, полковник Генерального штаба А. Д. Нечволодов назначается в Корею военным агентом, чтобы принять негласную агентурную сеть, уже созданную подполковником Л. Р. фон Раабеном. Однако в январе 1904 года в Порт-Артуре, на пути к месту службы, Александра Дмитриевича застала Русско-японская война.
В штабе Манчьжурской армии, возглавляемой генералом Куропаткиным, Александру Дмитриевичу поручается организация дальней разведки. Уже в конце апреля 1904 г. из Ляояне он завербовал и направил в Японию и Корею нескольких тайных агентов, иностранных подданных.
После сражения при Ляоляне он попытался отправить, как представитель контрразведки при штабе наместника, во избежание гибели Манчжурской армии по вине Куропаткина[12] за что личным распоряжением Куропаткина отправлен «для поправления здоровья» в Приамурье. В штабе Приамурского военного округа Нечволодов формирует партизанские отряды и организует сбор разведсведений о возможных десантах врага.
После подписания Портсмутского договора Нечволодов возвращается в Петроград, в котором поднимается новый всплеск терроризма и начинает разжигаться революция 1905–1907 гг.