Родился в 1959 году в Луганской области. Вскоре семья переехала в Новокузнецк, где будущий литератор окончил школу, несколько лет работал столяром. Отслужив в рядах Советской Армии, Анатолий Остроухов поступил в Литературный институт имени М. Горького, по окончании которого в 1986 году приехал по распределению молодых специалистов в Тамбовскую область. До 1990 года работал в Никифоровской районной газете, затем два года учился на Высших сценарных курсах Госкино СССР.
С 1988 года Анатолий Остроухов окончательно переселился в Тамбов. Здесь, в Книжной лавке писателя, у него вышло несколько сборников: "В бедном свете вокзальном", "Волчье эхо", "Звезда одинокая". Проза и киносценарий печатались в "Рассказ-газете".
Он - лауреат премии имени Г. Д. Ремизова.
Анатолий Остроухов живет и работает в Тамбове.