Андрей Демченко родился в Запорожье, где и начал свою футбольную карьеру. С развалом Союза переехал в Россию и стал играть в ЦСКА. Привлекался в юношеские и молодежные сборные России, подавал большие надежды. А в 1994 году после юношеского чемпионата Европы в Испании (на котором блистали Клюйверт, Рауль, де ла Пенья, Давидс) при помощи тогдашнего своего агента Константина Сарсании (и тут без него не обошлось, хотя это была его первая сделка) поехал на двухнедельные смотрины в амстердамский «Аякс». Голландцы его подписали, хотя и не без трудностей. На первый год ему предложили зарплату в 5 тысяч долларов в месяц, а он хотел 15. Ему показали контракт Клюйверта, подписанный годом ранее на 3 тысячи, а исходя из того, что в клубе контракт пересматривали каждый год, с Демченко нужно было торговаться. Наш думал 3 часа, и все никак не решался подписать контракт, и на то были причины, ведь лучшего бомбардира ЧЕ хотели также видеть «Бавария», «Штутгарт» и «Фиорентина». В итоге пришел тогдашний тренер Луи Ван Галь и дал игроку всего 15 (по другим данным 3) минут на размышление – наш согласился. Контракт подписали на 3,5 года.
В первом же сезоне «Аякс» выиграл Лигу Чемпионов, потом становился чемпионом Голландии. Звездный час Андрея был в матче Суперкубка Европы против «Сарагосы», тогда он чуть не забил. Но время шло, ушел Ван Галь, а Андрей так и оставался молодым, подающим надежды игроком среди таких звезд как Клюйверт, де Буры, Блинд, Мусампа, Воутерс, Финиди, Литманен, Овермарс, Зеедорф, Давидс, Райкаард и другие. Пришел датчанин Мортен Ольсен, который не видел его в составе и не хотел продлевать контракт с Андреем, о чем ему заявили незадолго до начала чемпионата Голландии. Времени на трудоустройство в Европе оставалось мало, хотя до этого у него были предложения из Испании и Голландии. В «Аяксе» тогда началась революция, когда Де Буры отказались
Такому повороту способствовало еще и то, что у Демченко не было своего агента. Удивительный случай, как для легионера в таком именитом клубе.
Демченко психанул, и вернулся домой, а вскоре начал играть в запорожском «Металлурге» в котором начинал. Предложения из Европы были, и все же стоило остаться в Европе, с его опытом школы «Аякса» он бы смог нормально играть до сих пор в той же Голландии.
