Футболом розпочав займатися з першого класу в ДЮСШ міста Чернівці. Перший тренер — Ігор Калита, потім — Володимир Нікітін[1]. У 15 років перейшов у місцеву «Ладу»[2]. Пізніше розпочав грати в молодіжній команді чернівецької«Буковини». У 1999 році став членом основної команди «Буковини» й зіграв у складі цієї команди один матч. В середині 2000 року перейшов у куп'янський«Оскіл» і за один сезон відіграв у трьох матчах за цей клуб. В середині 2001 року перейшов у золочівський«Сокіл», в якому за один сезон відіграв у 15 матчах. У сезонах 2002—2003 років грав за івано-франківський«Спартак» і калуський«Спартак-2».
Через конфлікт з тренером Богданом Блавацьким на початку сезону 2004 року перейшов у сумський «Спартак-Горобина» і за півтора сезони зіграв у 23 матчах. Проте через фінансові проблеми в сумському клубі в середині 2005 року повернувся в івано-франківський«Спартак» і виступав за цей клуб до середини 2006 року. Після чого перейшов у дніпродзержинську «Сталь» і зіграв за цей клуб у 25 матчах, по завершенні сезону отримав запрошення від охтирського клубу «Нафтовик-Укрнафта», зіграв 6 матчів у вищій лізі України. В другій половині сезону 2007/08 року виступав у «Комунальнику» з Луганська. Напередодні початку сезону 2009/10 років повернувся до рідної «Буковини» з Чернівців[3].
На початку 2010 року підписав контракт з зарафшанским«Кизилкумом» з Узбекистану, який виступав у Вищій Лізі чемпіонату Узбекистану. За «Кизилкум» Андрій Мельничук виступав до середини 2011 року і за цей час зіграв у 33 матчах. В цей час до нього надійшла пропозиція від самаркандського«Динамо», й він підписав контракт з цим клубом. У складі «Динамо» Мельничук став одним з лідерів команди і основним воротарем.
Пізніше став і капітаном команди[4]. Виступав за самаркандське «Динамо» до кінця 2015 року. У той же час 2015 році в Узбекистані видали указ, що воротарі-легіонери з наступного року не мають права грати в чемпіонаті. Можливо, якби він змінив громадянство, то ще не завершував би кар'єру, а пропозицію щодо зміни громадянства отримував неодноразово, так само як і грати і за національну збірну Узбекистану. Однак завжди вирішував, що він українець і його Батьківщина - Україна, тому грати за іншу країну було б неправильно[5].
У 2016 році почав тренерську діяльність, в тому ж році отримав тренерську ліцензію «С» УЄФА. У 2017 закінчив навчання в школі тренерів для професійних гравців (ліцензія «А + В» УЄФА). Працював в академії кам'янської «Сталі», тренував юнацький «Металург» (Кам'янське) і «Маолдіс» (Дніпро) виступавші у всеукраїнській лізі юніорів. З липня по
2019 року очолював рідну «Буковину»[6][7]. Надалі працював у ДЮСШ «Спарта» (Чернівці) та аматорській команді «Довбуш». З 2022 року знову очолює головну команду рідного краю: Буковину.
Україна
