Один из самых высокооплачиваемых спортсменов России — его ежегодный заработок в «Юте Джаз» составлял около 15,3 миллионов долларов.
8 августа 2008 года Андрей был удостоен чести нести флаг России на открытии летних Олимпийских игр в Пекине.
В 2011 году Кириленко получил гражданство США.
Андрей Кириленко родился 18 февраля 1981 года в Ижевске. Профессионально баскетболом начал заниматься в Санкт-Петербурге. В 1995 году в составе команды города стал чемпионом России среди игроков 1981 года рождения.
18 января 1997 года в составе питерского «Спартака» Кириленко дебютировал в чемпионате России, став в неполные 16 лет самым юным игроком первенств в истории. Летом 1998 года игрок перешел в ЦСКА, с которым выиграл два чемпионата России. В сезоне 2000/01 Кириленко вместе со своей командой вышел в «Финал четырёх» Супролиги ФИБА.
30 июня 1999 года Кириленко был выбран клубом НБА «Юта Джаз» под 24-м номером драфта. В то время россиянин был самым молодым европейским баскетболистом, задрафтованным командой Национальной баскетбольной ассоциации.
В «Юте» Кириленко дебютировал в сезоне 2001/02, по итогам которого был включён в символическую пятерку лучших новичков НБА. Перед началом сезона 2003/04 команду покинули ее многолетние лидеры Джон Стоктон (завершил карьеру) и Карл Мэлоун (перешёл в «Лос-Анджелес Лейкерс»). После этого Кириленко стал ведущим игроком «Юты Джаз».
В середине сезона 2004/05 Кириленко получил тяжёлую травму руки и вернулся на площадку лишь осенью 2005 года. Сезон 2005/06 стал для россиянина самым удачным в карьере. Он стал лучшим игроком НБА по общему числу блокшотов (220), а также сделал два трипл-дабла.
В сезоне 2006/07 показатели Кириленко значительно ухудшились: главный тренер «джазменов» Джерри Слоун строил атакующую игру команды через других игроков. Сам баскетболист в интервью российским СМИ неоднократно заявлял, что если командная игра «Юты» не изменится, он не исключает своего перехода в другой клуб. Однако россиянин остался в команде.
В сезоне 2007/08 Кириленко играл в стартовой пятёрке во всех играх регулярного чемпионата и плей-офф и набирал в среднем 11 очков за игру.
В сезоне 2009/10 показатели Кириленко были не столь высокими из-за травм — он пропустил большую часть регулярного сезона и первый раунд плей-офф против «Денвер Наггетс» и сумел восстановиться лишь ко второму раунду плей-офф против «Лос-Анджелес Лейкерс», где Кириленко провёл две игры.
По окончании сезона 2010/11 Андрей Кириленко стал свободным агентом. В связи с локаутом в НБА 4 октября 2011 года подписал трёхлетний контракт с ЦСКА Москва, в случае окончания локаута он мог вернуться в НБА. 31 декабря 2011 года стало известно, что Андрей Кириленко будет выступать за ЦСКА до конца сезона.
За национальную сборную Кириленко дебютировал в 2000 году на Олимпиаде в Сиднее. Играл на Чемпионатах Европы 2001, 2003, 2005, 2007 годов, Чемпионате мира 2002.
Памятным для Кириленко стал Евробаскет 2007 в Испании. Сборная России впервые в своей истории (без учета достижений команды СССР) стала победителем первенства континента. Кириленко провел несколько ярких матчей, лучшим из которых стал полуфинал с Литвой (86:74). В этой встрече форвард набрал 29 очков, реализовав 9 из 11 бросков с игры. По итогам турнира Андрей был включен в символическую сборную турнира и признан MVP турнира. Андрей также выступал на Олимпийских играх в Пекине и был знаменосцем сборной России на церемонии открытия Игр.
В 2009 году Кириленко отказался принять участие в Евробаскете 2009 по семейным обстоятельствам.
В 2010 году Андрей Кириленко принял решение не участвовать на чемпионате мира по баскетболу 2010 года.
В 2011 году вернулся в сборную для участия в чемпионате Европы, на котором сборная России заняла 3-е место.
Андрей Кириленко является универсальным игроком, который может выступать на позиции лёгкого или тяжёлого форвардов. Известен высокий уровень его игры как в нападении (12,4 очка и 5,6 подбора за игру в карьере НБА по окончании сезона 2010/2011), так и в обороне. В атаке Кириленко опирается на набирание фолов соперниками, игру в пас и свой быстрый первый шаг. За умение играть в обороне его три раза включали в сборную всех звёзд защиты НБА. Основной силой оборонительной игры Кириленко являются блокировка бросков и умение перехватить мяч (2,0 блок-шота и 1,4 перехвата за игру в карьере НБА по окончании сезона 2010/2011).
Благодаря своей универсальности Андрей трижды за карьеру в НБА достигал очень редкого статистического показателя, который в Северной Америке называют «пять-по-пять» (англ. Five-by-five), когда баскетболист за матч набирает не менее 5 баллов по каждому статистическому показателю — очкам, передачам, подборам, перехватам и блок-шотам. Андрею дважды удался «пять-по-пять» в течение одной недели в начале декабря 2003 года, а 3 января 2006 года в игре против «Лос-Анджелес Лейкерс» ему удалось достичь показателя «пять-по-шесть», когда он набрал не менее 6 баллов по каждому показателю. За всю историю начиная с сезона 1985/86 лишь Хакиму Оладжьювону удалось «сделать» «пять-по-шесть». Оладжьювон также единственный баскетболист, кроме Кириленко, которому удалось за карьеру достичь более одного показателя «пять-по-пять» — у знаменитого центрового их 6.
Андрей женат на Марии Лопатовой, дочери баскетболиста Андрея Лопатова. Мария старше мужа на 8 лет. У них в семье трое детей — сыновья Фёдор, Степан и дочь Александра, которую удочерили в 2009 году. Жена баскетболиста в 2002 году записала музыкальный диск, а сам Кириленко снялся в клипе супруги.
Андрей является двоюродным братом теннисистки Марии Кириленко.
Во время сезона НБА чета Кириленко живёт в собственном доме в Солт-Лейк-Сити, а в межсезонье живёт в Москве и во Франции. Супруги Кириленко создали благотворительный фонд «Kirilenko’s Kids», оказывающий помощь детским домам, интернатам, больницам и спортивным школам США и России.
9 февраля 2012 года был официально зарегистрирован как доверенное лицо кандидата в Президенты РФ Михаила Прохорова.