Мостовий починав грати у великий футбол ще за радянських часів. Вихованець московського ЦСКА, він привернув увагу майбутнього наставника «Спартака» Олега Романцева, який у середині 80-х набирався досвіду в московській команді другої ліги «Красна Пресня». Мостовий опинився в «Пресні», а потім разом з Романцевим пішов на підвищення і перебрався до «Спартака». Був чемпіоном Радянського Союзу в 1987-му та 1989 роках, у складі молодіжної збірної країни виграв чемпіонат Європи в 1990-му, того ж року перейшов до національної команди, яку після відставки Валерія Лобановського очолив Анатолій Бишовець. А в 1991 році вирушив за кордон, прийнявши пропозицію португальської «Бенфіки». Відтоді протягом півтора десятка років виступав за кордоном, де встиг обзавестися родиною. На початку цього року стало відомо, що Мостовий вирішив повісити бутси на цвях, чим дав привід згадати свою не найбіднішу на події зарубіжну кар'єру.
Мало хто знає, але того ж 1991 року Мостовий практично підписав контракт з леверкузенським «Баєром», у складі якого нині виступає українець Андрій Воронін. Мостовий побував у Німеччині і домовився про умови майбутньої угоди з керівництвом клубу. Однак у Москві його знайшов Василь Кульков, який уже півроку грав у лісабонській «Бенфіці» разом із Сергієм Юраном. Партнер Мостового по «Красній Пресні» та «Спартаку» запропонував своєму другові прилетіти до нього в гості до Португалії. З'ясувалося, що Мостовим зацікавилося керівництво «Бенфіки». Після кількох днів тренувань з командою він отримав пропозицію від керівництва клубу підписати контракт. Присутність у «Бенфіці» старих знайомих і гучне ім'я клубу зіграли головну роль у рішенні Олександра.
Обираючи між німецьким та португальським клубами, він зупинився на останньому, про що потім відверто шкодував. Спочатку Мостовий півроку чекав, поки його заявлять для участі в чемпіонаті країни. А коли це нарешті сталося, з «Бенфіки» пішов шведський спеціаліст Свен-Горан Ерікссон (нині тренер збірної Англії), який запрошував Олександра до команди. Його місце зайняв відомий тренер Томіслав Івич. Кульков і Мостовий не вписувалися в його схему гри і змушені були більшу частину часу проводити на лаві запасних. Мостовий серйозно задумався про зміну клубу, і навіть звільнення Івича не змінило його планів. Але контракт із «Бенфікою» підписали на цілих чотири роки. Саме цей період кар'єри Олександр вважає найневдалішим.
Вихід із становища все-таки знайшовся наприкінці 1993 року. Керівництво французького «Кана» звернулося до босів «Бенфіки» з проханням віддати їм Мостового в оренду до кінця сезону. «Кан» ішов на передостанньому місці і потребував «джокера» — футболіста, якого запрошують для посилення клубу. Ставка на Мостового, зроблена «Каном», повністю виправдалася. У першому ж матчі він забив гол, і команда вперше в сезоні здобула перемогу. Завдяки Олександру «Кан» покинув зону вильоту і закінчив сезон у середині турнірної таблиці. Після закінчення чемпіонату, у 1994 році, тренер «Кана» Жанделю отримав вигідну пропозицію від іншого французького клубу, «Страсбура», і вмовив Мостового перейти разом із ним.
Нова команда виявилася трохи сильнішою за попередню. Варто зазначити, що за неї виступав відомий Франк Созе (переможець Ліги чемпіонів у складі «Марселя»). Два сезони Мостовий відіграв у «Страсбурі» просто блискуче, і його постійно включали до всіляких символічних збірних за підсумками чемпіонату. Надходили й привабливі пропозиції від сильних французьких, іспанських та німецьких команд. Однак президент «Страсбура» вирішив будь-якою ціною залишити Мостового у своїй команді і став вести подвійну гру. Він обіцяв Олександру, що готовий за відповідну суму відпустити його в будь-яку команду. Але коли представники клубів, зацікавлених у придбанні Мостового, зверталися до президента «Страсбура» з конкретними пропозиціями, той запитував за Олександра астрономічні суми. За тиждень до закінчення періоду заявок гравців на Мостового та президента його клубу вийшли представники скромної іспанської «Сельти». І саме їм несподівано вдалося домовитися з обома.
«Господарі клубу порушували домовленості про розмір зарплати, — згадує футболіст. — Начебто не відмовлялися від своїх обіцянок, але затягували їх виконання. Я почав вести переговори з німецькими клубами — «Штутгартом» і «Кайзерслаутерном». Неодноразово начебто досягали згоди, але «Страсбур» в останній момент непомірно підвищував розмір компенсації за мене. Нарешті мої «господарі» здалися, але запропонували невідомий мені раніше клуб «Сельту» з невідомого мені міста Віго. Залишався тиждень дозаявок, і я ризикнув. Місто Віго хоч і невелике, але там один із найбільших у Європі портів. Тож гроші в клубу водилися, хоча він був і не в найкращому стані. Перший час я вважався чи не головним «смутьяном» — постійно нагадував керівництву клубу: «Що ж ви гроші витрачаєте на купівлю гравців, а не налагоджуєте інфраструктуру?». На той момент поля, база, роздягальні в «Сельті» були гіршими, ніж у більшості російських клубів вищої ліги, а можливо, і першої. Чи не нажив я цим собі ворогів? Перший час багатьох дратував. Але потім змирилися і навіть визнали справедливість моїх вимог. А через кілька років мене обрали капітаном команди…»
До приходу росіянина «Сельта», головним чином, вирішувала завдання виживання у вищій іспанській лізі. Після появи Мостового все змінилося. З «Сельтою» одразу почали рахуватися навіть гранди іспанського футболу «Реал» і «Барселона». У команду повірили вболівальники, а спонсори почали вкладати в неї гроші. Слідом за Мостовим у «Сельті» з'явилися й інші відомі гравці: ізраїльтянин Ревіво, бразилець Мазіньйо, француз Макелеле та ще один росіянин — Валерій Карпін. З приходом цих футболістів «Сельта» заграла в видовищний, комбінаційний футбол. А головну роль у команді відігравали два російські півзахисники. Не дивно, що «Сельту» називали «російською». Мостового у Віго майже все влаштовувало: і умови контракту (який може бути переглянутий лише у бік збільшення його суми), і ставлення до наших футболістів з боку вболівальників та журналістів, і той футбол, у який грає «Сельта».
Але настав 2004 рік, який виявився переломним для футболіста. Кар'єра Мостового пішла на спад. Почалося з того, що очільник збірної Росії Георгій Ярцев повернув футболіста до національної команди, яка з труднощами пробилася на чемпіонат Європи. Мостовий знову став одним із ключових виконавців збірної країни, але після першого ж матчу на Євро-2004, програного іспанцям, футболіста зі скандалом вигнали з тренувального табору. Причина — інтерв'ю, дане іспанським журналістам одразу після фінального свистка. Мостового звинуватили в поразницьких настроях, образі тренерського штабу та інших гріхах. Офіційне формулювання — «неетичні» та «несвоєчасні» висловлювання в пресі.
Сам футболіст стверджував, що нічого подібного не говорив, а його слова журналісти одного з провідних іспанських видань просто перекрутили. Мостовому довелося попрощатися зі збірною, за яку він завжди із задоволенням виступав. Після травми, отриманої в національній команді, керівництво «Сельти» наполегливо просило Олександра не виступати за російську збірну. Однак півзахисник заявив, що ніколи не відмовлявся і не відмовиться від виступів за збірну Росії.
Мостовий надто довго прожив за кордоном і, мабуть, забув звичаї, які панують у російському спорті. Начальник завжди правий, і з цим нічого не вдієш. Олександр же звик до можливості висловлювати свою думку, але при цьому ніколи не доводив справу до серйозного конфлікту. Навряд чи Ярцеву вдалося б навчити поводитися «по-іншому» 36-річного гравця, сформованої людини і вельми популярного футболіста, якому вболівальники іспанської «Сельти» збиралися поставити пам'ятник у центрі Віго.
Коли спалахнув скандал, журналісти згадали й те, що Мостовий, не попереджаючи про відлучку, нерідко досить несподівано зникав з розташування «Сельти». Мовляв, цей футболіст некерований, а тому нічого дивного в його витівці немає. Але, за великим рахунком, це не відповідає дійсності. Мостовий залишиться в пам'яті вболівальників і фахівців не скандалістом, а успішним футболістом, який завоював любов зарубіжних уболівальників і отримав прізвисько Русский Цар. А народну любов, погодьтеся, заслужити непросто.
Немає нічого дивного в тому, що цей дуже талановитий півзахисник, один із найкращих гравців у новітній історії російської збірної, став своїм на Заході. Мостовий — дуже комунікабельна людина, легко і досить швидко вивчав мови країн, у яких грав. Він добре володіє португальською, французькою та іспанською мовами.
Особисте життя Мостового, можна сказати, незвичайне. Перебравшись до «Бенфіки», щоб не вважатися легіонером у команді, йому довелося в 1991 році оформити фіктивний шлюб із громадянкою Португалії. Тоді ще існували обмеження на іноземців, а тому в «Бенфіки», як і в багатьох інших клубів, існували такі способи вирішення проблем. Згодом Мостовий зізнався, що так жодного разу зі своєю «дружиною» і не побачився. Розрив стосунків із португальською дружиною, про який ніхто ніколи не згадував, судячи з усього, стався після переїзду футболіста до Франції. А там Олександр познайомився зі Стефані — студенткою місцевого університету. Незабаром їй довелося перервати навчання — народився син, якого назвали Сашком. Через три роки, коли Мостовий уже грав у «Сельті», народилася донька Емма. Але потім сім'я розпалася. Деякі джерела стверджують, що сталося це в 2003 році. Причина — подружня зрада.
Тепер він — цілком вільна людина, не зайнятий тренуваннями і живе на власне задоволення — може дозволити собі поспати довше, піти куди завгодно, коли завгодно повернутися. Після Євро-2004 він пішов із «Сельти», керівництво якої залишилося винне йому чималу суму. Олександр стверджує, що цих грошей цілком вистачило б «на рік безбідного життя». Його звали підзаробити в Катар і Саудівську Аравію, в Росію. А він прийняв пропозицію скромного «Алавеса» з другого іспанського дивізіону. Бос цього клубу — Дмитро Пітерман — американець, народжений в Одесі. Але, провівши в цій команді лише один матч, попрощався. Каже, що з особистих причин.
Система мені сподобалася і, перебравшись до Франції, я попросив, щоб мені відкрили рахунок у місцевому банку. Мене повезли до BMP (є такий банк у Франції). Потім, поїхавши до Іспанії, залишив цей рахунок за собою. Я якось пробував відкрити ще один рахунок в іншому місці, але потім передумав. Так зручніше. Кажуть, що не можна всі яйця класти в один кошик, але я вважаю, що в житті можуть статися неприємності не лише з банком, а з чим завгодно. Якось безглуздо намагатися страхуватися від усіх можливих ризиків. Все одно не вийде. Можна вкласти гроші в акції або в нерухомість. Але й цей варіант не завжди надійний. А взагалі я працюю з різними фінансовими інструментами, але не сам, а за допомогою консультанта. Кредити? Так, в Іспанії багато хто бере кредит на 20-30 років і потім розплачується. Я на такий довгий термін грошей ніколи не позичав, але взагалі кредитом доводилося користуватися. Здебільшого на великі покупки».
Судячи з усього, жити Мостовий збирається в Іспанії. «Мені здається, що ця країна створена для того, щоб жити й отримувати від цього задоволення. Ось така вона зручна та комфортна…» Але при цьому він до кінця так і не став людиною із західним менталітетом. «Чи став я тут своїм? У душі точно залишився росіянином. Скільки років грав, живу за кордоном, але як думав російською, так і думаю. Як лаявся російським матом, так і лаюся. Я залишаюся російською людиною…»