Na svět přišel malý Andrej v městě, které se v té době jmenovalo Leningrad. Dnes se mu říká Sankt Petěrburg nebo Petrohrad. Zde po základní škole nastoupil na Matematicko-fyzikální školu (lyceum) č. 30, kterou dokončil roku 1981. Následujících šest let studoval na Leningradském vojenském mechanickém institutu, kde získal kvalifikaci v oboru dynamika letu a řízení. Poté byl dva roky zaměstnán u vojenského námořnictva.
Ke kosmonautice se Borisenko dostal roku 1989, kdy nastoupil do Raketové a kosmické korporace Eněrgija S. P. Koroljova (RKK Eněrgia). Postupně se vypracoval na pozici vedoucího směny ve středisku řízení letů Roskosmosu. Nejprve se staral o vesmírnou stanici Mir, později o Mezinárodní vesmírnou stanici (ISS).
Borisenkovi však časem nestačilo sledovat dění na oběžné dráze z řídícího střediska, ale chtěl se jej zúčastnit osobně. Přihlásil se proto do výběru kosmonautů a v září 2002 získal souhlasné stanovisko od lékařské komise. V lednu následujícího roku úspěšně složil požadované zkoušky a 29. května byl díky doporučení Státní meziresortní komise přijat do oddílu kosmonautů. Od června 2003 prodělal dvouletý výcvik, který zakončil 27. června 2005 s výborným hodnocením. Nedlouho poté mu byla přiznána kvalifikace „zkušební kosmonaut“.
Na oběžnou dráhu se Borisenko vydal kosmickou lodí Sojuz TMA-21, nesoucí jméno Jurij Gagarin. Start se uskutečnil 4. dubna 2011, jen několik dní před tím, než si celý svět připomněl padesáté výročí od prvního kosmického letu. Dalšími členy posádky byli Alexandr Samokuťajev a Ronald Garan.
Po dvou dnech se loď připojila k ISS a kosmonauté do ní přestoupili. Zde s třemi kolegy, kteří již na palubě stanice pobývali, utvořili tzv. Expedici 27, což bylo pojmenování posádky v období březen až květen 2011. Borisenko v ní pracoval jako palubní inženýr, tedy na stejné pozici jako v Sojuzu. Poté, co se původní trojice vrátila na Zem a vystřídali ji další tři kosmonauté, začala Expedice 28, kde Borisenko působil již jako velitel. V této době ISS naposledy navštívil americký raketoplán Atlantis během mise STS-135, což byl úplně poslední let programu Space Shuttle.
Borisenko, Samokuťajev a Garan svoji kosmickou výpravu ukončili 16. září 2011, kdy nasedli do stejného Sojuzu, jaký je v dubnu dopravil na oběžnou dráhu a po necelých 3,5 hodinách letu přistáli v Kazachstánu, asi 150 km od města Džezkazgan.
