Родился 9 мая 1980 г. в селе Калиновица (Варвинский р-н, Черниговская обл., Украинской ССР; ныне Украина). С пятилетнего возраста вместе с семьей проживал в Сочи.
В 2003 г. окончил факультет туризма, сервиса и спорта Сочинского государственного университета туризма и курортного дела (ныне - Сочинский государственный университет), впоследствии учился там же в аспирантуре факультета экономики и процессов управления. В Российском международном олимпийском университете (Сочи) прошел обучение по программе дополнительного профессионального образования "Мастер спортивного администрирования" (2013).
В детстве занимался каратэ, тхэквондо, джиу-джитсу, борьбой и гимнастикой.
В середине 1990-х - начале 2000-х гг. сменил ряд профессий: работал барменом, грузчиком, инкассатором, сборщиком компьютеров, программистом, официантом, телохранителем, юристом по оформлению грузовых поставок и др.
В 1999 г. одержал победу на конкурсе по армрестлингу "Железная рука города Сочи", одолев, среди прочих, чемпиона Европы Котэ Размадзе. После этого приступил к систематическим занятиям данным видом борьбы, тренером Воеводы стал Размадзе. В 2000 г. выиграл чемпионат мира по армрестлингу (Рованиеми, Финляндия). Впоследствии дважды повторил это достижение.
В бобслей пришел в мае 2002 г. Является одним из наиболее успешных российских представителей этого вида спорта: двукратный олимпийский чемпион (2014, Сочи - в "двойке" с Александром Зубковым и в "четверке" с Александром Зубковым, Алексеем Негодайло и Дмитрием Труненковым), обладатель серебряной (2006, Турин, Италия - в "четверке" в Александром Зубковым, Филиппом Егоровым и Алексеем Селиверстовым) и бронзовой (2012, Ванкувер, Канада - в "двойке" с Александром Зубковым) олимпийских медалей, чемпион мира (2011, Кенигсзее, Германия) и двукратный чемпион Европы (2008, Чезана, Италия; 2011, Винтерберг, Германия) в "двойке" с Александром Зубковым. Окончательно завершил карьеру бобслеиста в 2015 г., работал в ГБУ Краснодарского края "Центр спортивной подготовки по зимним видам спорта", занимал должность начальника сборных команд Краснодарского края.
В апреле 2010 г. вместе с Александром Зубковым адресовал президенту РФ Дмитрию Медведеву письмо, в котором призвал отправить в отставку руководство национальной федерации бобслея. В сентябре того же года Воевода намеревался принять участие в выборах членов президиума данной организации, однако ему было отказано в регистрации в качестве кандидата.
По данным СМИ, в июне 2016 г. бывший глава антидопинговой лаборатории в Москве Григорий Родченков сообщил Всемирному антидопинговому агентству, что в 2014 г. во время Олимпиады в Сочи Воевода якобы употреблял допинг. Спортсмен опроверг эту информацию, а также заявил, что "в Сочи была самая чистая, самая "белая" Олимпиада". Впоследствии был дисквалифицирован Международной федерацией бобслея и скелетона за нарушение антидопинговых правил на Олимпиаде в Сочи (срок отстранения - с 21 декабря 2018 г. по 20 декабря 2020 г.).
4 декабря 2011 г. баллотировался в Государственную думу РФ VI созыва по списку "Единой России" (№19, региональная группа №25, Краснодарский край), однако не прошел в нижнюю палату парламента.
В 2016-2021 гг. - депутат Государственной думы РФ VII созыва. Баллотировался 18 сентября 2016 г. по списку "Единой России" (восьмой номер в региональной группе №33, Краснодарский край). По итогам голосования в Думу не прошел. 28 сентября получил мандат Владимира Порханова (третий номер региональной группы №33), главврача краевой клинической больницы №1, после выборов отказавшегося от места в Думе. Воевода вошел в состав фракции "Единая Россия".
Член Всероссийской политической партии "Единая Россия".
Являлся послом XXII зимних Олимпийских игр в Сочи 2014 г.
Принимал участие в телевизионных шоу "Я смогу!" (2014, "Россия 1") и "Без страховки" (2016, Первый канал).
Член попечительского совета Ассоциации операторов фитнес-индустрии (2021).
Заслуженный мастер спорта России по армрестлингу (2004) и бобслею (2006).
Награжден орденом "За заслуги перед Отечеством" IV степени (2014), медалью ордена "За заслуги перед Отечеством" II степени (2010).
Почетный гражданин г. Сочи (2010).
Лауреат премии "Серебряная лань" Федерации спортивных журналистов России (2014).
Алексей Воевода - один из основных персонажей документального фильма "Борясь с Джоном" (2009, США, режиссеры Вассилики Консари и Севан Матоссиан).