Начинал в лыжной секции, выступал на первенство Куйбышевского района столицы. Тем не менее, стремился стать футболистом. С помощью друзей был принят в школу «Красный богатырь», где с первых игр был поставлен на ворота. Через год перешел в спартаковскую школу к Михаилу Огонькову. В «Спартаке» на тот момент не было вратаря, а у Прудникова были хорошие рекомендации. К тому времени Алексею было уже 15 лет.
Через 2 года, в 1978 году, принят в дубль московского «Спартака». В 1979—1982 годах сыграл только 17 матчей, был дублёром Дасаева. Из команды не уходил, поскольку видел, что нужен команде и тренеру Бескову.
В конце 1982 перешёл в «Динамо» (Москва), желая получить больше игрового времени. В 1983—1985 годах был основным голкипером при тренерах Вячеславе Соловьеве и Александре Севидове. С середины 1985, при новом главном тренере Эдуарде Малофееве, основного вратаря не было — Прудников и его дублер Уваров стояли по очереди, до пропущенного мяча. Только в конце сезона тренер отдал Прудникову полное предпочтение, признав, что тот действительно капитан команды.
В сезонах 1986 Прудников также был основным голкипером «Динамо». Вместе с клубом взял «серебро» в 1986 году. В середине 1987, узнав, что новый главный тренер Анатолий Бышовец пригласил в клуб Дмитрия Харина, попросил отпустить его из команды. После этого 4 месяца был без команды, поскольку постоянно был на выездах вместе с олимпийской сборной.
В начале 1988 года согласился на предложение «Торпедо». Тем не менее, по сути не играл — поскольку также чаще всего был на сборах с олимпийской командой. Между сборами провёл 5 матчей за торпедовцев.
На самой Олимпиаде в Сеуле Прудников не имел практически шансов выйти на поле, поскольку 1-м номером был Дмитрий Харин. Более того, Бышовец больше рассматривал его как помощника. Тем не менее, были 2 возможности появиться в играх Олимпиады. Однако, в матче с американцами получили желтые карточки Добровольский и Михайличенко и тренеры заменили их, а в финале он должен выйти на серию одиннадцатиметровых, но сборная в итоге справилась с бразильцами в дополнительное время.
После победной Олимпиады Бесков позвал Прудникова обратно в «Спартак». После некоторых сомнений Валентин Иванов отпустил Алексея в родную команду. Однако, к этому времени Бескова в «Спартаке» сменил Олег Романцев. Основным вратарём стал Черчесов, а Прудников за полтора года сыграл только 2 матча.
В середине 1990 года уехал в Югославию, где планировал выступать за мостарский «Вележ». В команду его пригласил один из руководителей команды, когда увидел Алексея в игре за команду спартаковских болельщиков в Мостаре. После одного контрольного матча, с Прудниковым был заключен контракт. Однако за клуб практически не играл, так как Федерация футбола СССР забыла выслать вовремя трансферный сертификат. К концу года ситуация усугубилась еще и финансовыми проблемами клуба. Прудникову предлагают перейти в «Сараево», перед которым стояла задача остаться в высшей лиге. В итоге данная задача была успешно выполнена.
В 1991 возвращается в Россию из-за начавшейся войны в Югославии, при этом на Балканах ему пришлось оставить дом и две машины. В середине 1992 по приглашению Александра Бокия стал играющим тренером чешского клуба 3-й лиги «Топольчаны». Однако в команде пробыл только полгода, поскольку в клубе начались финансовые проблемы. Всю первую половину 1993 года не играл, так как чехи не высылали трансферный сертификат. Все это время работал тренером вратарей московского «Спартака» по приглашению Олега Романцева. Одновременно занимался агентской деятельностью, помогал спартаковским футболистам уезжать в заграничные клубы.
На вторую половину 1993 уехал играть в финский «Яро», где ему предложили «отличные условия». Партнерами в команде были легионеры из СССР — Александр Воробьев и Алексей Еременко. По окончании сезона финны предложили контракт на новый сезон. Однако из-за долгого перерыва между сезонами (6 месяцев) и невозможностью все это время видеться с семьей, Прудников ответил отказом и вернулся в Россию.
В начале 1994 был на предсезонных сборах в «Локомотиве» (Москва), однако подписал контракт с калининградской «Балтикой».
В «Балтике» Прудников оказался благодаря околофутбольным проблемам. В начале 90-х он, вместе с футбольной командой эстрадных артистов «Старко», выступил учредителем фирмы «АлСтар» (название — производное от имен соорганизаторов). Фирма занималась производством профессиональных футбольных вратарских перчаток. Под открытие бизнеса был взят кредит в банке и к 1994 необходимо было его погашать. «Балтика» бралась решить эту проблему Прудникова, что и было прописано отдельным пунктом в контракте. Однако ни одно другое обязательство по контракту не было исполнено, что побудило Алексея расстаться с командой.
В середине сезона перешёл в краснодарский «Колос».
Игровую карьеру закончил в южнокорейском клубе «Чонбук Хёндэ Дайнос», выступая в роли играющего тренера.
Прудников сравнивал свой игровой стиль с Дасаевым:
В 2000 году был тренером по работе с вратарями в клубе «Самсунг Блю Уингз».
В 2001 году был главным тренером футбольного клуба звезд эстрады «Старко». С этого же года работал, с перерывами, тренером вратарей в московском «Спартаке». В 2006 году был спортивным директором вильнюсского клуба «Ветра».
Тренер вратарей ФК «Крылья Советов» (Самара) (с января 2010). В июле 2010 года лишен лицензии футбольного агента за нарушение регламента РФС (совмещение тренерской и агентской деятельности.
Директор СК «СиМ» (выступает в первенстве Москвы среди ЛФК).
Сын Алан также футбольный вратарь.