В 1885 году министр юстиции Д. Н. Набоков перевел способного юриста в центральный аппарат своего ведомства на должность редактора департамента. Здесь А. А. Хвостов пробыл довольно долго — почти четыре года и получил свою первую награду — орден Св. Владимира 4-й степени, а затем новый министр Н. А. Манассеин назначил его управляющим законодательным отделением. Приобретя большой практический опыт аппаратной службы, хорошо изучив действующее законодательство, Александр Хвостов сумел занять престижное место юрисконсульта. Когда во главе Министерства юстиции встал Н. В. Муравьев, Александр Алексеевич перешел на службу в Министерство внутренних дел, где занял должность правителя канцелярии министра. Министром тогда был И. Л. Горемыкин, с которым у А. А. Хвостова были давние дружеские отношения. При его преемнике Д. С. Сипягине он занял вначале пост чиновника особых поручений, а затем — директора хозяйственного департамента.
К этому времени к его наградам прибавились новые: ордена Св. Станислава 2-й и 1-й степеней, Св. Владимира 3-й степени и иностранные — Командорский крест Почетного Легиона и Австрийский орден Франца-Иосифа Командорского креста 2-й степени. Он много и плодотворно работал в различных комиссиях. В 1901 году А. А. Хвостов вернулся в лоно Министерства юстиции, где Муравьев предложил ему должность директора 1-го департамента. Он сменил С. С. Манухина, переведенного товарищем министра юстиции. Александр Алексеевич уже имел чин действительного статского советника, а вскоре он стал и тайным советником.
В начале 1905 года произошла смена министров юстиции. Муравьев получил давно вожделенное место Чрезвычайного и полномочного посла при Его Величестве короле Италии, а в его кресло 21 января сел Сергей Сергеевич Манухин. В тот же день последовал именной высочайший указ Правительствующему Сенату: «Директору Первого департамента, тайному советнику Хвостову Всемилостивейше повелеваем быть товарищем министра юстиции».
В конце 1905 года Александр Алексеевич, оставаясь в должности товарища министра, был пожалован в Сенаторы. В следующем году он получил очередную награду — орден Св. Владимира 2-й степени. Вскоре ему была объявлена высочайшая благодарность за труды, осуществленные в качестве члена Особого совещания по пересмотру установленных для охраны государственного порядка исключительных законоположений.
Товарищем министра юстиции он оставался и при А. Г. Акимове. В правительственных кругах А. А. Хвостов слыл человеком независимым и «убежденным законником». Не вполне сходясь во взглядах со своими шефами (С. С. Манухиным и А. Г. Акимовым), он, как писали тогда в одной из газет, «являл собою золотую середину, не вдаваясь резко ни вправо, ни влево, считая, что закон должен быть твердым и равным для всех, пока этот закон не изменен и действителен».
С назначением министром юстиции И. Г. Щегловитова, Александр Алексеевич оставил свою должность и стал лишь присутствовать в Правительствующем сенате. Сенатором он оставался почти шесть лет, получив в 1910 году орден Белого Орла. 1 января 1912 года А. А. Хвостов был назначен членом Государственного совета.
В область большой политики А. А. Хвостов вступил во время Первой мировой войны, в период так называемого министерского государства. Он был назначен министром юстиции и генерал-прокурором 6 июля 1915 года. Сам Хвостов так рассказывал об этом: «Я жил в деревне, когда получил из Вильно от возвращавшегося из Ставки И. Л. Горемыкина телеграмму с просьбой приехать в Петербург. Из телеграммы я понял, что меня желают экстренно привлечь в ряды, так сказать, действующей армии, и, думая, что Горемыкин хочет это сделать исключительно по своей инициативе, поехал в Петербург с определенной целью отказаться. По приезде я видел Горемыкина, предложившего мне, как единственному, по его словам, кандидату государя, пост министра юстиции. Считая себя обязанным исполнить высочайшую волю, я хотя и доложил государю, что болен, но сказал, что опасности в том, что через две недели принужден буду выбыть из строя — нет, и государю угодно было меня назначить министром юстиции. Чем была вызвана отставка моего предместника — я не знаю. Почему государь остановился на мне — думаю, что по представлению И. Л. Горемыкина, с которым я знаком еще со времен ревизии Сенатором Шамшиным Самарской и Саратовской губерний».
Во время войны, как отмечали современники, все правительственные перемещения все более и более приобретали «характер какой-то безумной министерской чехарды». Люди, приличные, дельные и честные удерживались на высоких постах недолго, а их места, как правило, занимали лица бездарные, беспринципные, а то и вовсе зловещие. В. Д. Набоков писал по этому поводу: «Чувствовалось дыхание безумия и смерти… Царь с самого начала войны и до катастрофы, постигшей его в первые дни марта 1917 года, абсолютно не отдавал себе отчета в роковом значении развертывающихся событий. Те, кто пережил в Петербурге зимы 1915–1916 годов, хорошо помнят, как с каждым днем нарастало сознание какой-то неизбежной катастрофы».
В такой обстановке назначение А. А. Хвостова министром юстиции с полным основанием можно отнести к наиболее удачным. После И. Г. Щегловитова, серьезно дискредитировавшего органы юстиции, во главе судебных и прокурорских учреждений встал человек, хотя и примыкавший к правому крылу и убежденный монархист, но в то же время уважительно относящийся к закону, честный, в меру скромный и принципиальный. В отличие от своего предшественника, он внимательно «присматривался и прислушивался» к подчиненным, чтил судебную независимость, не препятствовал проведению выборов членов суда, не делал незаконных перемещений судебных и прокурорских чинов.
Товарищ министра юстиции А. Демьянов писал о нем: «А. А. Хвостов — типичный бюрократ, но тоже из честных. Школу бюрократическую он прошел блестящую. Как умный и честный человек, он хорошо понимал, что юстиция на щегловитовском лакейском режиме держаться не может; то есть авторитет ее должен падать, не говоря уже о том, что и само дело юстиции не могло идти нормальным путем».
А. А. Хвостов сразу же предпринял попытки «почистить ведомство». Он начал приглашать в министерство порядочных людей, на преданность которых вполне мог бы рассчитывать. Он пробыл на посту министра юстиции и генерал-прокурора всего один год. Безусловно, он не сделал многого из того, на что был способен. И все же успел разрешить целый ряд проблем и устранить некоторые серьезные перегибы и разрушения, произведенные его предшественником. Одно из таких дел — рассмотрение вопроса о допущении в адвокатуру так называемых инородцев.
Деятельность А. А. Хвостова приходилась на военное время, отсюда многие циркуляры и распоряжения министра, его законопроекты касались именно этих обстоятельств. Война не обошла стороной и судебных работников. Многие из тех, кто покинул местности, занятые неприятелем, остались не у дел. Чтобы хоть как-то облегчить их положение, Хвостов внес в Совет Министров проект закона «о командировании эвакуированных должностных лиц судебного ведомства для усиления канцелярий Правительствующего сената и Министерства юстиции и установления военного и морского ведомств, в качестве юрисконсультов при заключении договоров по подрядам и поставках для нужд обороны».
При обсуждении в Совете Министров наиболее важных государственных вопросов А. А. Хвостов часто занимал принципиальную и твердую позицию. При этом он не отличался многословием и обычно не вступал в длительные дискуссии, а высказывал свое мнение ясно и достаточно кратко. В трудных случаях, когда нужно было встать на ту или иную точку зрения, откровенно признавался в своих сомнениях.
1916 год по праву можно назвать юбилейным. В этот год отмечалось 50-летие Петроградского и Московского судебных установлений, мировых судов и присяжной адвокатуры. Торжества начались 17 апреля в Петрограде. Здание суда в день 50-летия введения Судебных уставов в столице приняло торжественный вид. Всюду были разостланы ковры и ковровые дорожки, отремонтированы некоторые помещения, приведена в порядок и отреставрирована мебель. В два часа дня в суд прибыли А. А. Хвостов, член Государственного совета Н. Н. Шрейбер, Сенатор А. Ф. Кони и другие высшие чины государственных и судебных органов.