Генерал поселился на окраине Белграда, в Душеновце, в маленьком, плохо меблированном домике из трех комнат, которые занимали он сам с женой, брат Борис, адъютант и верный вестовой Федор. До центра было около часа ходьбы, но это Кутепова не смущало, он любил подолгу ходить пешком. Сразу же по прибытии в Белград Александру Павловичу сообщили ошеломляющую новость: в соответствии с приказом П. Н. Врангеля большинству чинов 1-го армейского корпуса отныне позволялось наниматься на работу. И пусть такое решение было единственно верным и возможным со стратегической точки зрения, для Кутепова оно означало только то, что его корпус больше не существует как военная сила, а его чины теперь просто беженцы, наемники, а сам он уже никому не нужен. Это еще больше оттолкнуло Кутепова от Врангеля. Предоставленные ему должности «помощника главнокомандующего» и «начальника Галлиполийской группы в Болгарии» не могли обмануть Александра Павловича, так как за ними не стояло ничего конкретного. Кутепов все больше и больше склонялся к тому, что фигурой, объединяющей военную эмиграцию, должен быть не Врангель, а великий князь Николай Николаевич — Верховный главнокомандующий в 1914–1915 годах, ныне проживавший в имении Шуаньи недалеко от Парижа и многими признававшийся главой дома Романовых.

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

В феврале — марте 1923 года состоялась первая поездка Кутепова в Париж, во время которой генерал дважды, 9 и 28 марта, общался с великим князем и, по утверждению Б. А. Штейфона, «принял на себя известные деловые обязательства» по организации боевой работы в Советской России. Официальный перевод Кутепова в распоряжение великого князя Николая Николаевича состоялся 21 марта 1924 года, когда приказом П. Н. Врангеля № 14 Александр Павлович был освобожден от должностей помощника главнокомандующего и начальника Галлиполийской группы. И хотя второй параграф этого приказа содержал исключительные похвалы Кутепову, генерала этот документ больно задел, ведь его фактически увольняли из армии. «Вот и дослужился, что меня перевели на беженское положение», — обмолвился он в разговоре. Когда Кутепов уезжал из Белграда в Париж, его провожали всего лишь пять человек.

Отношения между Кутеповым и Врангелем так и остались холодными. Они по-прежнему были между собой на «ты», но Петр Николаевич высказывался о дальнейшей деятельности Александра Павловича в лучшем случае скептически, а в худшем называл ее «подлой игрой» (в письме П. Н. Шатилову 26 января 1926 года).