Родился 9 августа 1963 г. во Владивостоке.
Андрей Тарасенко окончил отделение подводного плавания Нахимовского военно-морского училища в Ленинграде (ныне Санкт-Петербург), в 1985 г. - Высшее военно-морское училище подводного плавания им. Ленинского комсомола (в 1998 г. объединено с Высшим военно-морским училищем им. М. В. Фрунзе в Санкт-Петербургский военно-морской институт), в 2002 г. - Российскую академию государственной службы при президенте РФ (ныне Российская академия народного хозяйства и государственной службы при президенте РФ) по специальности "государственное и муниципальное управление" с присвоением квалификации "менеджер". В 2006 г. получил диплом Российского государственного социального университета по специальности "бухгалтерский учет, анализ и аудит" с присвоением квалификации "экономист".
Имеет диплом капитана.
Доктор психологических наук. В 2003 г. в Московском государственном социальном университете защитил диссертацию на соискание ученой степени кандидата психологических наук на тему "Диалоговая модель принятия управленческих решений руководителем". В 2009 г. в Российском государственном социальном университете защитил докторскую диссертацию на тему "Социально-психологические закономерности и механизмы оптимальной деятельности военного руководителя".
В 2010 г. присвоено ученое звание профессора по кафедре акмеологии и кибернетики.
До 1994 г. проходил военную службу в Вооруженных силах СССР и РФ. После окончания училища был направлен на Черноморский флот, в Балаклаву (в составе г. Севастополя). Позднее, по словам самого Андрея Тарасенко, был командиром подводной лодки специального назначения, служил на военной базе Камрань (Вьетнам).
С сентября 1997 г. по январь 2000 г. работал управляющим ЗАО "Вестморепродукт".
С января 2000 г. по ноябрь 2003 г. - и. о. генерального директора, генеральный директор ФГУП "Национальные рыбные ресурсы" ("Нацрыбресурс") при Государственном комитете РФ по рыболовству (ныне Федеральное агентство по рыболовству). В функции предприятия входила, в частности, продажа квот на добычу морепродуктов отечественным и иностранным компаниям.
В ноябре 2001 г. стал членом коллегии Госкомитета РФ по рыболовству.
С января 2004 г. по июнь 2005 г. исполнял обязанности директора Мурманского морского рыбного порта.
С июля 2005 г. по июнь 2007 г. – заместитель начальника инспекции по контролю расходов федерального бюджета на рыболовство и водные ресурсы департамента контроля расходов федерального бюджета на природопользование и агропромышленный комплекс Счетной палаты РФ.
С июня по август 2007 г. работал первым заместителем директора Научно-исследовательского института химических реактивов и особо чистых химических веществ.
С декабря 2007 г. по апрель 2008 г. – заместитель начальника управления делами и административного обеспечения Федерального агентства по атомной энергии, затем, до февраля 2010 г. - заместитель директора департамента управления делами и имущественным комплексом Государственной корпорации по атомной энергии "Росатом".
С декабря 2010 г. по январь 2012 г. работал в ОАО "Россельхозбанк", занимал должности от главного экономиста до советника заместителя председателя правления банка.
С марта 2012 г. по июнь 2013 г. - заместитель руководителя, руководитель Невско-Ладожского бассейнового водного управления Федерального агентства водных ресурсов.
С 27 июня 2013 г. был заместителем генерального директора, одновременно с 1 июля 2013 г. - и. о. генерального директора ФГУП "Росморпорт". Предприятие занимается эксплуатацией и содержанием федерального имущества в морских портах, а также предоставлением услуг по обеспечению безопасности мореплавания в акваториях морских портов и на подходах к ним.
С 11 сентября 2013 г. Андрей Тарасенко занимал пост генерального директора ФГУП "Росморпорт".
4 октября 2017 г. указом президента РФ был назначен врио губернатора Приморского края, сменив на посту руководителя региона Владимира Миклушевского.
9 сентября 2018 г. принял участие в выборах губернатора Приморского края от партии "Единая Россия". Набрал 46,56% голосов и вышел во второй тур вместе с кандидатом от КПРФ, депутатом краевого парламента Андреем Ищенко (24,63%). 16 сентября 2018 г. во втором туре выборов Андрей Тарасенко получил, по данным избиркома, 49,55% голосов избирателей, Андрей Ищенко - 48,06%. При этом в ходе предварительного подсчета голосов кандидат от КПРФ опережал главу региона на 3-7%. Оба соперника обвинили друг друга в нарушениях избирательного законодательства. 19 сентября ЦИК России рекомендовал крайизбиркому отменить итоги выборов. 20 сентября региональная избирательная комиссия признала недействительными результаты второго тура из-за "невозможности достоверно определить волеизъявление граждан". Андрей Тарасенко заявил, что не будет участвовать в повторных выборах губернатора Приморья.
26 сентября 2018 г. Андрея Тарасенко на посту главы Приморского края сменил Олег Кожемяко, который ранее возглавлял Сахалинскую область.
С 27 сентября 2018 г. по 1 августа 2020 г. Андрей Тарасенко был заместителем руководителя Федерального агентства морского и речного транспорта (Росморречфлот).
31 июля 2020 г. был назначен врио председателя правительства Республики Саха (Якутия).
С ноября 2020 г. по октябрь 2023 г. - председатель правительства Якутии.
С 9 ноября 2023 г. занимал пост врио генерального директора ФГУП "Нацрыбресурс", подведомственного Федеральному агентству по рыболовству.
С 29 марта 2024 г. - руководитель Федерального агентства морского и речного транспорта. Сменил во главе ведомства Захария Джиоева.
Андрей Тарасенко был членом советов директоров АО "Ленморниипроект" (Санкт-Петербург) и судостроительного завода "Красное Сормово" (Нижний Новгород).
Капитан 1 ранга.
Действительный государственный советник РФ III класса (2020).
Награжден орденом Дружбы (2023), медалью ордена "За заслуги перед Отечеством" I степени.