Започва кариерата си във Факел, а след това играе в Динамо Вологда. През 1982 заминава за Москва, където изкарва казармата и получава звание Младжи лейтенант. Отборът, в който играе, е Динамо (Москва). Бородюк е един от основните играчи на отбора, като печели купата на СССР, става 2 пъти голмайстор и е олимпийски шампион от олимпиадата в Сеул през 1988. Треньорът Анатолий Бишовец започва да налага по-младите Игор Коливанов и Сергей Киряков и Александър е продаден на запад.
През 1989 подписва с намиращия се тогава във Втора Бундеслига на ФРГ Шалке 04. Бородюк и украинецът Владимир Лютий стават първите играчи от съюза, подписали договори с отбор от ФРГ. В първия си сезон с екипа на „миньорите“ Бородюк става втори голмайстор на тима с 16 попадения. На следващия сезон Шалке се връща в Бундеслигата, а Александър става голмайстор на отбора с 13 гола. В бундеслигата резултатността на Бородюк се свежда до 6 – 7 гола на сезон, а и конкуренцията на поста му се усилва. През януари 1994 е продаден на Фрайбург за 500 000 марки. Там обаче Бородюк е резерва и не успява да покаже най-доброто от себе си. През 1996 е даден под наем на Хановер 96.
През 1997 Юрий Сьомин го привлича в Локомотив със свободен трансфер. С Локо Бородюк играе полуфинал за КНК и става вицешампион на Русия. Също така успява да стане член на Клуб 100 и Клуб „Григорий Федотов“. След това играе по 1 сезон за Торпедо-ЗИЛ в 1 дивизия и за Криля Советов. Завършва кариерата си на 39 години, като в последния си сезон играе като либеро.
През 2001 става асистент на Александър Тарханов в Криля Советов. От 2002 е помощник-треньор на националния отбор на Русия, като през 2006 е временен треньор на отбора. От лятото на 2012 отново е временен треньор на Русия. След това за няколко месеца е спортен директор на Динамо Москва, но е заменен от Дмитрий Галямин през ноември 2012.
