Андрей Мельничук родился 3 января 1954 года в городе Корсаков Сахалинской области. В 1979 году окончил исторический факультет Пермского государственного университета, в котором впоследствии занимал должность старшего преподавателя, затем доцента кафедры древней и новой истории России.
С 1995 года Мельничук занял должность руководителя Камской археологической экспедиции. С 2001 года был научным консультантом Камской археологической экспедиции. Одно время входил в состав Учёного совета Пермского краевого музея.
Андрей Фёдорович - автор более 100 статей, посвященных проблемам археологии разных периодов древней истории Пермского края, биографиям местных археологов. Он исследовал ряд памятников древней истории Среднего Приуралья: стоянка Горная Талица, поселение Огурдино, стоянка Новожилово, стоянка Чашкинское озеро IV, жертвенное место у Писаного камня на реке Вишере, Гремячинское святилище, Гляденовское городище (костище), Мокинский могильник, Деменковский могильник и Городище Сёминское.
В мае 2003 года Камской археологической экспедицией с консультантом Мельничук, было исследовано древнейшее поселение на территории исторического центра Перми - палеолитическая стоянка Егошиха, существовавшая здесь в 15 - 12 тысячелетиях до нашей эры, близ впадения речки Стикс в речку Егошиху. Было собрано несколько тысяч разнообразных каменных орудий, по которым установлено, что обитатели стоянки охотились на благородных оленей и лошадей-мустангов.