Анатолій Борисенко народився у Запоріжжі. Розпочав займатися футболом у місцевому СДЮШОР при клубі «Металург». У 1985 році розпочав залучатися до основної команди «Металурга», яка грала в радянській першій лізі, проте за рік зіграв лише в одному матчі Кубка СРСР. У 1986 році Борисенко грав у складі команди радянської другої ліги«Торпедо» із Запоріжжя, а в 1987 у складі команди другої ліги СКА (Київ). У 1988 році футболіст повернувся до «Металурга», проте в цьому році в основному складі так і не зіграв, і наступного року грав у складі команди другої ліги «Кристал» з Херсона. У 1990 році Анатолій Борисенко перейшов до складу аматорської команди «Титан» з Армянська, яка у 1992 році грала в українській перехідній лізі. а з сезону 1992—1993 років грала в другій українській лізі. Борисенко відразу став одним із найрезультативніших гравців армянської команди. У 1993 році футболіст спочатку переходить до складу іншої команди другої ліги «Дружба» з Бердянська, у складі якої зіграв лише 1 матч в Кубку України, після чого знову стає гравцем запорізького «Металурга». Цього разу футболіст зіграв 6 матчів у вищій українській лізі, в яких відзначився 1 забитим м'ячем, і знову з початку 1994 року повернувся до «Титан». У сезоні 1994—1995 років Борисенко з 23 забитими м'ячами став кращим бомбардиром другої ліги, після чого отримує запрошення до іншої команди вищої ліги «Карпати» зі Львова. Після 2 проведених матчів за львівський клуб футболіст повертається до Армянська.
Під час сезону 1996—1997 років Анатолій Борисенко переходить до складу команди першої ліги«Металург» з Маріуполя, та виходить разом із ним до вищої ліги. Після проведеного сезону у вищій лізі Борисенко повертається до «Титана», проте вже не був гравцем основного складу, і фактично до закінчення виступів на футбольних полях виконував роль граючого тренера.
У 2004 році з серпня по жовтень Анатолій Борисенко був головним тренером «Титана» з Армянськ. З липня 2005 до травня 2006 року Борисенко знову очолював тренерський штаб армянської команди, після чого до червня 2012 року працював одним із тренерів клубу. З 2009 року Борисенко працював тренером ДЮФШ «Титан» (Армянськ).
Україна
СРСР