Несколько месяцев А. Я. Сухарев, числясь еще на военной службе, занимал должность начальника отдела Воронежского военного окружного управления связи. После демобилизации в июле 1946 года он устроился на строительный участок № 2 Вагоноремонтного завода имени Тельмана, где занимался воспитательной работой среди молодежи. В марте 1947 года его направили на комсомольскую работу. К этому времени А. Я. Сухарев был уже студентом Всесоюзного юридического заочного института.
В течение последующих одиннадцати лет Александр Яковлевич постепенно поднимался по ступеням комсомольской аппаратной иерархии: был заведующим отделом пионеров и вторым секретарем Железнодорожного райкома комсомола г. Воронежа, инструктором и заместителем заведующего отделом пропаганды и агитации Воронежского обкома ВЛКСМ. В сентябре 1950 года его переводят в Москву, в Центральный Комитет ВЛКСМ. Через два месяца после этого он окончил ВЮЗИ и получил диплом юриста. В аппарате Центрального Комитета комсомола Александр Яковлевич занимал должности инструктора, ответственного организатора, заведующего сектором, заместителя заведующего отделом комсомольских органов и, наконец, в апреле 1958 года, стал заведующим международным отделом ЦК ВЛКСМ. На этой должности он пробыл полтора года. А. Я. Сухарев принимал активное участие в подготовке всех крупнейших мероприятий, проводившихся под эгидой Центрального Комитета, в том числе VI (Москва, 1957 год) и VII (Вена, 1959 год) Всемирных фестивалей молодежи и студентов, за что получил несколько Почетных грамот ЦК ВЛКСМ. В 1956 году он был награжден орденом «Знак Почета» за участие в освоении целинных земель.
В декабре 1959 года А. Я. Сухарева выдвинули на еще более высокий пост — в аппарат Центрального Комитета КПСС. Здесь он работал более десяти лет, первое время занимая должность инструктора, а затем заместителя заведующего отделом административных и торгово-финансовых органов ЦК КПСС по РСФСР. В 1966 году он стал заведующим сектором отдела административных органов ЦК КПСС.
В сентябре 1970 года Александр Яковлевич переходит на работу в органы юстиции. Тогда только что было воссоздано Министерство юстиции СССР, ликвидированное еще в середине 1950-х годов по инициативе Н. С. Хрущева. Вместо него долгое время существовала безликая и фактически бесправная юридическая комиссия при Совете Министров СССР. Министерство юстиции СССР возглавил В. Теребилов, работавший до этого в Прокуратуре Союза ССР, а впоследствии — заместителем Председателя Верховного суда СССР. Постановлением Совета Министров СССР от 22 сентября 1970 года А. Я. Сухарев назначается первым заместителем министра и членом коллегии Министерства юстиции СССР. Одновременно с ним заместителями министра стали также председатель Московского городского суда Н. А. Осетров и начальник отдела общего надзора Прокуратуры Союза ССР А. А. Холявченко.
Александр Яковлевич, имевший к этому времени солидный партийный опыт, занимался в министерстве кадровой работой, организацией правовой пропаганды и установлением связей с партийными и советскими органами. Он возглавлял также Межведомственный координационный совет по правовой пропаганде при Министерстве юстиции СССР. При его содействии был основан популярнейший журнал «Человек и закон», членом редакции которого он был долгое время (тираж достигал 12 миллионов), появилась телевизионная передача с таким же названием (особенно популярной она была, когда ее вел известный писатель, доктор юридических наук, профессор А. А. Безуглов). Именно в те годы в школах и профтехучилищах стали в обязательном порядке изучать основы советского права. Активно шла также демократизация судопроизводства, повышалась культура судебных процессов, преодолевались остатки культа личности в правовой науке. Ко всем этим процессам Александр Яковлевич имел самое непосредственное отношение.
В системе министерства юстиции А. Я. Сухарев прослужил почти 18 лет. До 1984 года он был первым заместителем министра юстиции СССР, а затем — министром юстиции РСФСР. За это время он защитил диссертацию в Академии общественных наук и получил ученую степень кандидата юридических наук (1978 год). К его наградам прибавились новые. В 1967 и 1971 годах он награжден двумя орденами Трудового Красного Знамени, а затем удостоился орденов Октябрьской Революции (декабрь 1977 года), Дружбы народов (сентябрь 1983 года) и Отечественной войны 1-й степени (1985 год). В октябре 1973 года Президиум Верховного Совета РСФСР наградил его Почетной грамотой, а в апреле 1987 года присвоил почетное звание «Заслуженный юрист РСФСР». Он избирался также депутатом Верховного Совета РСФСР (1984 год).