В сентябре 1881 г. Анатолий Мордвинов был принят в Николаевский кадетский корпус, в который чуть ранее, но в более низший класс, поступил его брат Павел. В октябре 1888 г. Анатолий Мордвинов окончил обучение в корпусе и, как это тогда называлось, «вступил в службу». В том же году он поступил в Николаевское кавалерийское училище, из которого был выпущен 10 августа 1890 г. в чине корнета и определен на службу в лейб-гвардии Кирасирский Ее Величества полк. Полк имел давнюю и славную историю. Сформирован он был еще в 1704 г. и назывался тогда Драгунским Иоганна Данееля Портеса полком. В свое время шефами полка были великий князь и престолонаследник Петр Федорович, будущий император Петр III (с 1742 по 1762 г.), императрица Мария Федоровна (с 1796 г.). При восшествии на престол императора Александра II полк был назван лейб-кирасирским Ее Величества, а с ноября 1894 г. получил название лейб-гвардии Кирасирского Ее Величества государыни императрицы Марии Федоровны полка. За подвиги, совершенные в период войны 1812 г., полк был награжден 22 георгиевскими трубами.
О раннем периоде службы Анатолия Мордвинова известно мало, и в этом нет ничего удивительного – служба шла обычным порядком, как у всех офицеров того времени: в 1894 г., то есть через четыре года после окончания училища, он был произведен в поручики. С одной стороны, служба в полку Мордвинову нравилась и вполне устраивала его, а с другой – заставляла задумываться о своем предназначении как командира. Именно желание стать профессиональным офицером подвигло его на то, чтобы в 1896 г. подать рапорт о поступлении в Николаевскую академию Генерального штаба. Любопытно, что после окончания Академии в 1898 г. и уже по прошествии продолжительного времени Мордвинов, как он сам о том пишет, пришел к выводу, что «офицерам Генерального штаба возвеличиваться совсем не приходится». В том же 1898 г. А. А. Мордвинову было присвоено звание штабс-ротмистра.
В 1899 г. в Гатчинском дворце, неподалеку от которого был расквартирован лейб-гвардии Кирасирский Ее Величества государыни императрицы Марии Федоровны полк, он познакомился со своей будущей супругой Ольгой Карловной Хис, дочерью Карла Иосифовича Хиса (Charles Heath).
Карл Иосифович (его отчество по существовавшей тогда традиции произносилось и как Осипович) был личностью легендарной. В 1877 г. уже в довольно преклонном возрасте он поступил на службу при дворе цесаревича Александра Александровича в качестве воспитателя и преподавателя английского языка августейших детей. Среди его учеников и воспитанников был и будущий император Николай II, которому в то время исполнилось 9 лет.