Родился в семье учёных — выпускников МГУ, отец — астрофизик, лауреат Государственной премии за работы по созданию Баксанской нейтринной обсерватории (1998), мать — химик, специалист по ядерному магнитному резонансу. Раннее детство провёл в коммунальной квартире на площади Ногина, впоследствии семья переселилась в отдельную квартиру в Малом Ивановском переулке.
В старших классах сменил несколько школ, аттестат о среднем образовании получил в 1983 году, в формировании строгого и точного математического мышления отмечал влияние учебника по геометрии под редакцией Колмогорова.
В том же году поступил на механико-математический факультет МГУ. Получив из-за сильной аллергии «белый билет» — освобождение от срочной воинской службы, отсрочку от которой не предоставляли прервавшим обучение в вузе, взял академический отпуск, после возвращения из которого был отчислен, но впоследствии восстановился.Во время учёбы в университете увлёкся алгебраической геометрией, в числе причин указывал на работу в этой области таких интересных людей, как Игорь Шафаревич. Во время академического отпуска подрабатывал преподавателем программирования на учебно-производственном комбинате, там встретился с Георгием Шабатом. Шабат познакомил Воеводского с Программой Гротендика (фр. Esquisse d"un programme), к которой впоследствии неоднократно обращался в своём творчестве, к осмыслению и развитию идей программы относятся и первые научные исследования Воеводского, проведённые совместно с Шабатом и вылившиеся в ряд публикаций, одна из которых получила одобрение Гротендика.
В 1989 году, по результатам I семестра четвёртого курса, несмотря на наличие опубликованных работ в ведущих журналах, окончательно отчислен из университета за академическую неуспеваемость.
В 1989—1990 годы опубликовал несколько работ вместе с Михаилом Капрановым, вскоре иммигрировавшим в США.
В 1990 году Капранов заполнил за Воеводского заявку на поступление в аспирантуру Гарвардского университета, и, несмотря на формальное отсутствие высшего образования, был принят. Квалификационный экзамен, на сдачу которого отводятся первые три года обучения в аспирантуре, сдал уже через месяц после поступления, благодаря чему был освобождён от занятий и смог сконцентрироваться на исследовательской работе. Находясь в аспирантуре постоянно нарушал регламенты: уезжал в Россию на 4 месяца, жил прямо в офисе, отказываясь снять жильё, при этом руководство факультета во всех случаях содействовало сохранению перспективного учёного в Гарварде. Докторскую диссертацию на тему «Гомологии схем и ковариантных мотивов» защитил в 1992 году под руководством Давида Каждана.По окончании аспирантуры прошёл годичную постдокторантуру в принстонском Институте перспективных исследований, после чего вернулся в Гарвард и три года состоял в Обществе стипендиатов (англ. Society of fellows), в которое ежегодно набирают 8 выпускников аспирантур и предоставляют возможность сфокусироваться на исследованиях, не отвлекаясь на преподавание.
В 1995 году женился на математике Надежде Шалаби (род. 1966), в браке, который завершился разводом в 2008 году, родились двое дочерей (Тали и Дина).
С 1996 по 1999 год работал в должности экстраординарного профессора (англ. associate professor) в Северо-Западном университете, где сотрудничал с крупнейшими специалистами по алгебраическойK{displaystyle K}-теории Андреем Суслиным и Эриком Фридландером (англ. Eric Friedlander), также в течение этого периода был приглашённым профессором в Институте Макса Планка и в Гарварде.
В 1998 году прочёл пленарный доклад «ТеорияA1{displaystyle mathbf {A} ^{1}}-гомотопий» на Международном конгрессе математиков в Берлине.
В 1998 году приглашён на постоянную позицию в Институт перспективных исследований; в январе 2002 года, за несколько месяцев до награждения медалью Филдса, получил должность пожизненного профессора института. Во время работы в Принстоне обращался к математической биологии в части исторической генетики и к теории вероятностей, работая над переформулировкой её на языке теории категорий, считая важным внести вклад в приложения, а в период 2005—2006 годов полностью выключился из академической деятельности.
В 2006 году опубликовал первые заметки по возможностям применения геометрических понятий к теории типов, и, после окончательного доказательства гипотезы Блоха — Като в 2010 году, полностью погрузился в новое направление, выдвинув программу унивалентных оснований.
К программе постепенно подключился значительный коллектив специалистов по математической логике, теории категорий, системам автоматического доказательства. Академический год 2012/13 в Институте перспективных исследований по инициативе Воеводского был объявлен «годом унивалентных оснований» , в рамках которого в сотрудничестве Воеводского, Ауди (англ. Steve Awodey) и Кокана была открыта специальная исследовательская программа, собравшая около 30 учёных, совместно написавших за этот период 600-страничную книгу.Умер у себя дома в Принстоне, обнаружен по обращению бывшей жены, которая некоторое время не могла с ним связаться и знала о тяжёлом заболевании; по её сообщениям, причиной смерти могла быть аневризма. Похоронен 27 декабря 2017 года на Химкинском кладбище в Москве.