Анатолий Герасимов родился в Москве в 1945 году, окончил музыкальную школу по классу кларнета, самостоятельно освоил саксофон, в 1960-е играл во многих московских группах, а также в биг-бэндах Анатолия Кролла, Юрия Саульского, Эдди Рознера, Бориса Рычкова. Стал известен после выступления на московском фестивале "Джаз-68". Во время пребывания в Москве оркестров Дюка Эллингтона и Тэда Джонса-Мела Льюиса познакомился с американскими музыкантами, которые помогли ему найти работу после переезда в США, пишет Colta.ru.
"Он стал типичным московским джазменом, готовым играть в любом ансамбле или оркестре и в любом стиле от традиции до авангарда, - написал о Герасимове Алексей Баташев в статье на конверте альбома As Time Flies. - Он много занимался и постоянно раскрывался новыми гранями. Помнится, как-то по радио прозвучала целая программа Толиных композиций и аранжировок, исполненная оркестром Юрия Саульского, - это было так свежо, талантливо, интересно. И если его манило что-то впереди, он легко снимался с места. Сунув под мышку сопрано с флейтой, он мог смотать в другой город на интересный джаз-фестиваль или просто на джем-сейшен".
"В начале 70-х к нам приехали два лучших американских бэнда - Эллингтона и Джонса-Льюиса, и Толя ездил вслед за ними, не отходил от них, играл вместе при малейшей возможности, дарил свои партитуры, что-то перенимал, учился. Но дела, как и у многих джазменов, не шли, и в один прекрасный день Анатолий Александрович Герасимов, русский, холостой, беспартийный, пошел в синагогу, придумал себе еврейскую бабушку, но вместо Тель-Авива улетел в Нью-Йорк", - цитирует статью Баташева сайт Jazz.ru.
В 1973 году Герасимов эмигрировал в США через Италию, где играл с пианистом Романом Муссолини (сыном Бенито Муссолини) и выдающимся кларнетистом Тони Скоттом. В Нью-Йорке Герасимов был принят в оркестр Дюка Эллингтона, много гастролировал в Америке и за ее пределами. Сотрудничал с музыкантами ансамблей Мерсера Эллингтона, Теда Джонса, Мела Льюиса, Майлса Дэвиса, Джорджа Бенсона, работал с Четом Бейкером, Жако Пасториусом, Джоном Скофилдом, Элвином Джонсом, писал музыку для кино и телевидения.
К началу 80-х годов Герасимов добился того, чего не достигал еще ни один русский музыкант - стал звездой джазовой сцены Нью-Йорка и был включен в знаменитую энциклопедию Jazz Legends.
В 1983 году Герасимов переехал в Париж, где начал сотрудничать с музыкантами фри-джаза и этно-джаза. В 1995 году вернулся в Москву и создал квартет (Юрий Погиба - клавишные инструменты, Антон Ревнюк - бас-гитара, Дмитрий Севастьянов - ударные), сотрудничал с группой "Аукцыон", выступал на фестивалях "Джазовая провинция-98" и "Памяти Сергея Курехина" (Нью-Йорк, 1998). В 1997 году Россия вернула ему гражданство.