Первая такая поездка состоялась в 1906 г. для принятия участия в церемонии коронации короля Норвегии Хокона и королевы Мод. На пути в Норвегию великокняжеская яхта «Полярная звезда», на которой находилась российская делегация во главе с великим князем Михаилом Александровичем, сделала короткую остановку в Дании, что позволило Анатолию Мордвинову впервые лично познакомиться с датской королевской семьей, родственниками вдовствующей императрицы Марии Федоровны. Наиболее яркие впечатления остались у Мордвинова от поездки в Великобританию и от личных встреч с королем Эдуардом VII.
Необходимо отметить, что А. А. Мордвинову как адъютанту великого князя было предписано сопровождать его не только в официальных, но и в приватных поездках. Так, летом 1907 г., когда у Михаила Александровича возникли серьезные проблемы со здоровьем (сильные боли в области желудка и печени), Анатолию Мордвинову пришлось выехать вместе с ним в Карлсбад для проведения консультации с известным в то время профессором Норденом>4.
В начальный период службы в качестве личного адъютанта у Анатолия Мордвинова сложились очень доверительные, почти дружеские отношения с великим князем. Еще больше эти отношения укрепились в период нахождения великого князя в Орле, куда он был направлен в 1909 г. в качестве командира 17-го Черниговского полка. Назначение в Орел было попыткой императора Николая II отослать своего брата подальше от Петербурга, где у Михаила Александровича в 1907 г. завязался роман с женой одного из его подчиненных – ротмистра Владимира Вульферта – Натальей Сергеевной, урожденной Шереметьевской.
Против этого очередного увлечения Михаила Александровича была настроена практически вся императорская семья, считавшая, что Наталья Сергеевна ни по своему положению в обществе, ни по жизненному опыту – брак с Вульфертом был у нее уже вторым – ни в коей мере не подходила великому князю. Именно эта любовь оказалась для Мордвинова роковой в истории его отношений с великим князем и сыграла большую роль в дальнейших взаимоотношениях между ним и Михаилом Александровичем и, более того, привела эти некогда напоминавшие братские отношения к почти полному разрыву. Еще в конце 1908 г. флигель-адъютант почувствовал, что «великий князь стал за этот год менее откровенен со мной… он чувствует, насколько я не одобряю всего того, что происходило за последние месяцы»