Дед А. А. Харлампиева — Георгий Яковлевич Харлампиев — был выдающимся гимнастом и кулачным бойцом. Он много лет собирал, изучал и классифицировал различные приёмы боя, борьбы и самозащиты. Будучи чрезвычайно сильным, он пальцами мог порвать монету в три копейки. Существует легенда, что его будущая жена однажды ехала на тройке и лошади понесли; катастрофа казалась неминуемой. Однако по той же улице гулял Георгий Яковлевич, который смог остановить тройку — так они и познакомились.
Отец — Аркадий Георгиевич Харлампиев — с отличием окончил Академию художеств и был послан на обучение в Париж за государственный счет. Через некоторое время он остался без средств и, чтобы продолжить учёбу, начал выступать на профессиональном европейском ринге. Вскоре стал чемпионом Франции, а затем и Европы, в абсолютной категории. Вернувшись в Россию, по прошествии времени стал родоначальником российской, а затем и советской школы бокса.
В шестилетнем возрасте Анатолий Аркадьевич, которого тренировали дед и отец, выступал в воздушной гимнастике под куполом цирка. В шестнадцать лет он был уже зрелым бойцом и весьма разносторонним спортсменом.
В то время он работал в Коммунистическом университете трудящихся Востока (КУТВ) и Обществе строителей Международного красного стадиона (ОСМКС) преподавателем физической культуры и подрабатывал в одном из московских театров, обучая актёров сценическому движению.
В КУТВе собрались профессиональные революционеры из стран Дальнего Востока, в том числе из Китая и Монголии. Многие из них владели боевыми искусствами, и у Анатолия Аркадьевича была возможность регулярно с ними практиковаться. Боролся он и с татарами (национальная поясная борьба). Ещё до того он в совершенстве овладел французской борьбой, английским и французским боксом; фехтовал, бегал, был великолепным акробатом и альпинистом высокого класса. Лично знал таких выдающихся борцов как Поддубный, Буль, Спуль и др.
В течение ряда лет Анатолий Аркадьевич ежегодно выезжал в среднеазиатские и кавказские республики, где ещё сохранились национальные виды борьбы. Он изучал их, систематизировал приёмы и методы тренировки, для чего боролся на состязаниях сам, иногда по много часов подряд. При весе в 72 кг, используя свое мастерство, он иногда побеждал бойцов в два раза тяжелее него.
По мотивам этих путешествий А. А. Харлампиева в 1983-м году был снят фильм «Непобедимый».
Уже будучи выдающимся мастером, Харлампиев изучал классическое дзюдо под руководством друга отца, Василия Сергеевича Ощепкова, который долго жил в Японии и тренировался в школе дзюдо Кодокан.
В 1938 году борьба самбо обрела официальный статус, и Харлампиев возглавил Федерацию самбо СССР, однако развитие нового вида борьбы было приостановлено Великой Отечественной войной. В первые же её дни Харлампиев ушел добровольцем на фронт; его служба была отмечена многими наградами. Закончив войну на Дальнем Востоке, он учился борьбе уже у японских пленных, в обозе которых было десять татами для дзюдо.
После войны продолжил свою работу по распространению и развитию самбо. Уже после ухода с поста главы федерации, Харлампиев оставался общепризнанным лидером этой борьбы и имел непререкаемый авторитет в этой области.
Также Анатолий Аркадьевич являлся преподавателем кафедры физической культуры МЭИ.