Поглощенный изменениями в собственной жизни, новоявленный граф Остерман, очевидно, не сразу оценил перемены в стране, вызванные смертью Екатерины II и восшествием на престол ее сына Павла I. Более опытные и искушенные соотечественники сразу же почувствовали в этом событии грядущие бедствия России, коснувшиеся в первую очередь армии. Не случайно знаменитый фельдмаршал Румянцев, услыхав о внезапном приезде фельдъегеря из Петербурга, горестно сказал: «Знаю, что это значит!» При чтении послания Павла I, извещавшего о смерти императрицы, полководца хватил удар, от которого он вскоре скончался. Смерть одного «из стаи славных екатерининских орлов» на пороге нового царствования была символичной…
Последнее тридцатилетие XVIII века было наполнено громом побед русской армии. «Российский меч во всех концах вселенной блещет…» — с восторгом писал Державин. Но в России существовал человек, которого победы россиян едва ли не раздражали, у которого единственным кумиром был полководец Фридрих II, не раз битый русскими войсками. Большим несчастьем для Отечества являлось то, что человек этот был не кто иной, как русский император Павел I.
С первых же дней своего царствования он стремился подогнать русские войска под устаревшие прусские образцы, и с 1796 года в армии за основу обучения был принят с некоторыми изменениями прусский устав 1760 года, отразивший уровень развития европейского военного искусства 50-летней давности. В числе лиц, обязанных руководствоваться предписаниями «нового» устава, был и А. И. Остерман-Толстой. Читая этот документ, он невольно думал о том, что для императора и его гатчинских сподвижников опыт побед русских войск за минувшее тридцатилетие как будто и не существовал, как будто чья-то невидимая рука хотела злобно перечеркнуть славное боевое России и его, Остермана, прошлое. Это были злоба и мстительность людей, которым не удавалось проявить себя в военную пору, потому что их нравственные качества были низкими, а военное мастерство — ничтожным. Их путь лежал в Гатчинские войска Павла I, где вахт-парад считался настоящим сражением, а за военное искусство принималась «наука складывания плаща, ибо не далее простирались их сведения» в этом вопросе. Слепое повиновение воле императора и тупую страсть к маршированию на плацу эти люди отождествляли со службой Отечеству. Не зная тягот войны, они не знали и истинной цены русскому солдату, относились к нему с бессмысленной жестокостью. Остерман-Толстой с болью узнавал от прежних сослуживцев по Преображенскому полку, как во время учений любимец Павла генерал Аракчеев, добиваясь образцовой выправки солдат, не стеснялся бить их палкой, рвал усы у старых гренадер, назвал перед строем заслуженных полков их овеянные славой знамена екатерининскими юбками. Остерман-Толстой понимал, что выговорить такие слова мог человек, не проливавший кровь под этими знаменами.
1 февраля 1798 года Остермана неожиданно назначили шефом Шлиссельбургского мушкетерского полка с производством на 27-м году жизни в чин генерал-майора. В этом случае значение имели не личные заслуги, а убеждение Павла I в том, что шеф полка должен быть непременно в чине генерала. И сам Александр Иванович чувствовал, что это было мнимое благополучие. Он не умел служить за страх, а за совесть. Для армии павловского времени он был человеком неудобным. В один из дней этого беспокойного царствования он явился по вызову во дворец, где услышал то, чего давно ожидал. Один из приближенных Павла I объявил господам генералам, штаб- и обер-офицерам, что государь император, хотя знает, как многие из вас ознаменовали себя отличными услугами, однако же службою вашею весьма недоволен и приказал мне вам сказать, что за малейшую ошибку по службе в строю каждый из вас будет разжалован вечно в рядовые солдаты. Тот, кто с честью служил, с честью службу может оставить, словом, государь изволил сказать: «Ищите себе место».
18 апреля 1798 года Остерман-Толстой был «переименован в действительные статские советники для определения к статским делам». Такой поворот событий его не особенно огорчил. Он был еще очень молод и верил, что у него все впереди. Кроме того, он чувствовал, что не одинок в постигшей его участи. С ноября 1796 по март 1801 года его судьбу разделили 2156 офицеров, 333 генерала и 7 фельдмаршалов, среди которых находился и Суворов, ставший в те годы символом отечественных боевых традиций, знаменем всех, кто был противником «опруссачивания» русской армии. «Русские прусских всегда бивали, что же тут перенять?» — говорил старый полководец, и его слова эхом разносились по России. И, сам того не желая, Павел I добился, что тысячи людей невольно осознали свое идейное братство, преданность суворовской школе военного искусства, которая сформировала их не только боевые, но и человеческие качества, среди которых на первом месте был патриотизм. В одном строю с теми, кто оказался выше павловских «нововведений», находился и А. И. Остерман-Толстой.