Начала играть в теннис с 5 лет.
Когда ей было 12 лет, её заметила во время тренировки заслуженный мастер спорта Елена Брюховец. Через год Брюховец предложила Марии работать вместе. Была разработана специальная трехгодичная программа, и менее чем за 3 года Кириленко стала первым номером в своей возрастной группе и второй в возрастной группе до 18 лет. Евгений Кафельников, Андрей Ольховский и Максим Мирный помогали Кириленко в организации тренерского процесса и поездках на турниры.
В 2002 Кириленко становится одной из самых юных победительниц первенств Канады и США, среди спортсменов не старше 18 лет.
С сентября 2002 года участвует во взрослых турнирах WTA. Быстро прогрессирует в мировом рейтинге, но этому мешает травма, полученная Кириленко в 2004 году.
Выиграла свой первый титул в турнирах WTA в 2005, одолев в финале China Open Анну-Лену Грёнефельд 6-3, 6-4.
На Уимблдоне в 2006 году была посеяна под 17 номером, но проиграла в первом же круге японке Синобу Асагоэ.
В 2007 году Мария Кириленко стала победительницей теннисного турнира Sunfeast Open, который проходил в Калькутте. В финале она за 67 минут разгромила украинку Марию Корытцеву 6-0, 6-2.
В 2008 году Мария стала победительницей турнира Hansol Korea Open, проходивший в Корее. В финале она одолела австралийку Саманту Стосур со счетом 2-6, 6-1, 6-4.
В 2010 году Мария дошла до четвертьфинала Australian Open, где уступила китаянке Чжэн Цзе. В парном разряде, где с ней выступала Агнешка Радваньская, она достигла полуфинала.
Подруга Марии Шараповой.
Встречалась с теннисистом Игорем Андреевым , с которым также выступала в миксте; позже встречалась с хоккеистом Александром Овечкиным.