Мельник родился в селе Воля Якубова, ныне являющемся частью Львовской области, а тогда входившим в состав Австро-Венгрии. О его родителях известно не очень многое. Мать вскоре после родов умерла, отец женился вторично, но вскоре умер сам. В итоге Андрея воспитывала его мачеха. Судя по всему, семья была далеко не бедной, поскольку Мельник выучился не только в гимназии, но и в Высшей школе агрономов в Вене.
Вскоре после окончания его учебы началась Первая мировая война. Как образованный человек, Мельник был мобилизован в офицерском звании и возглавил сотню сечевых стрельцов. В сентябре 1916 года попал в плен и был отправлен в лагерь военнопленных в районе Царицына (ныне Волгоград). Там и состоялось судьбоносное знакомство с прапорщиком ландвера Евгением Коновальцем, с которым они в дальнейшем станут самыми близкими соратниками.
Мельник и группа других офицеров в январе 1917 года бежала из лагеря и направилась в Киев. Что они делали следующие месяцы, неизвестно. Только осенью 1917 года, после того как в Киев приехал выбравшийся из лагеря Коновалец, Мельник вместе с ним занялся созданием Галицко-буковинского куреня сечевых стрельцов.
Основой отряда стали бывшие военнопленные. Сечевики должны были стать опорой Центральной рады, в частности, именно им была доверена ее охрана. Возглавил сечевиков Коновалец, начальником штаба стал Мельник.
После разгона Рады и прихода к власти гетмана Скоропадского сечевики были распущены. Тем не менее их офицерам было разрешено сформировать в Белой Церкви новый Отдельный отряд сечевых стрельцов, который вновь возглавили Коновалец и Мельник. Сечевики не отличались лояльностью к гетману и составили костяк вооруженного восстания против Скоропадского.
Мельник некоторое время числился начальником штаба армии УНР, но в целом старался быть поближе к другу. После всех злоключений гражданской войны остатки петлюровцев были интернированы в Польше, а Мельник перебрался в Чехословакию. Там Коновалец начал создание Украинской войсковой организации — подпольного националистического движения, актив которого состоял из ветеранов, прошедших Первую мировую и Гражданскую войны.
Мельник вернулся в Галицию, где стал краевым комендантом УВО, но скоро был арестован польской полицией и отсидел 4 года за подпольную антипольскую деятельность.
При Коновальце он неизменно входил в руководящий состав УВО и ОУН, совмещая это с легальной деятельностью (хотя после отсидки на некоторое время приостановил активную подпольную деятельность).
В свободное от политики время Мельник служил управляющим владениями у митрополита грекокатолической церкви Шептицкого, с которым находился в близких отношениях. Вероятно, связи с Шептицким помогли ему избежать репрессий в 30-е годы, когда ОУН* подверглась разгрому со стороны польской полиции.
После гибели Коновальца от рук советского агента Судоплатова возникла необходимость выбрать нового лидера организации. Самой очевидной кандидатурой на эту должность был Мельник. Он не только был старейшим соратником и близким лидером Коновальца, но и родственником, поскольку они были женаты на родных сестрах.
В августе 1939 года в Риме прошел Второй Великий Сбор ОУН, на котором полномочия Мельника были подтверждены. Они стали даже более широкими, чем у Коновальца. Тот был просто лидером организации, а Мельника провозгласили лидером украинской нации.
Формально мало что ограничивало власть Мельника в организации, однако на деле руководство сосредоточили в своих руках четыре человека: Мельник, Сциборский, Барановский и Сеник.
Однако на Сборе отсутствовали лидеры галицкой части ОУН*, сидевшие в польских тюрьмах. У них по поводу Мельника было свое мнение, они уже давно начали противопоставлять свою краевую организацию верхушке. Причем к политическому конфликту примешивался еще и конфликт поколений.
Через несколько недель после окончания сбора освободились галицкие лидеры и тут же попытались осуществить маленький переворот.
Бандера и сплотившиеся вокруг него соратники потребовали от Мельника убрать из руководящих органов Сциборского, Сеника и Барановского на том основании, что они польские шпионы и им не может быть веры. Стоит отметить, что все трое были старыми соратниками Коновальца и по сути воплощением бывшего руководства УВО и ОУН*.
Мельник организовал партийный суд, который не нашел никаких доказательств их работы на разведку. В ответ Бандера обвинил Мельника и всех его сторонников в предательстве и создал свою собственную ОУН*, которая получила название «революционной». Позднее, чтобы не путать две организации, изначальную ОУН* стали называть «мельниковцами», а революционную — «бандеровцами», в честь их лидеров.
Так начался великий раскол украинского националистического подполья, который так никогда и не был преодолен.
По идеологическим вопросам они не имели никаких разногласий, вопрос был в том, кому доверить лидерство. Плюс были некоторые тактические расхождения, но достаточно минимальные. Мельник считал, что необходимо опереться на немцев, а там уже смотреть, как будет складываться ход войны. Бандера же считал, что надо поскорее поднять восстание и провозгласить независимость, пока обе стороны отвлечены на войну, а там уже ориентироваться по обстоятельствам.
Различие в тактике было следствием сильных и слабых сторон каждой из фракций.
Мельник имел неплохие связи с немцами еще со времен УВО, которое при Коновальце пользовалось поддержкой немцев против поляков. Мельник был известен немцам, они его знали, и он мог договориться с ними о сотрудничестве. Однако на местах ячейки мельниковцев были не так сильны, их влияние было значительным в эмигрантской среде.
Бандера, наоборот, был неизвестен немцам и вряд ли мог бы в нормальных обстоятельствах заручиться их поддержкой ввиду полной неуправляемости. Зато у него был очень сильный актив на местах, особенно в галицких селах и городах.
Оба свои возможности переоценили.
Бандера никакого восстания поднять не смог, а Мельник ничего существенного от немцев не получил. Однако связи помогли ему остаться на свободе. Когда мельниковцы и бандеровцы, направившие в УССР свои походные группы начали в тылу у вермахта ожесточенно сводить друг с другом счеты и убивать, немцы арестовали Бандеру и его сподвижников, а Мельник остался на свободе.
Однако у немцев на Украину были свои планы, и даже то немногое, что еще разрешалось мельниковцам, вскоре было запрещено.
В августе 1941 года Мельнику разрешили сформировать из буковинских украинцев Буковинский курень, который должен был стать самостоятельным подразделением. Но уже к концу года курень расформировали, а его личный состав направили в отряды вспомогательной полиции. Это было явное понижение статуса. Из фактически самостоятельной полуармии мельниковцы были низведены до шуцманов и полицейских, которых набирали в обычных селах. Вместо борьбы за независимую Украину во главе с Мельником их отправили искать евреев и партизан.
Никаких постов Мельник не получил, ему пришлось довольствоваться только тем, что несколько мельниковцев стали бургомистрами и старостами нескольких оккупированных городов и сел.
С конца 1943 года, когда стало понятно, что немцы проигрывают, Мельник сменил тактику.
Актив на местах начал понемногу включать в свою пропаганду антинемецкие лозунги и призывы, что не осталось незамеченным немцами. В январе 1944 года Мельник вместе с несколькими соратниками был арестован немцами. Впрочем, ему еще повезло, что немцы знали его и посадили в спецблок для политических заключенных в Заксенхаузене, где условия были относительно сносными. Его соратнику Ольжичу-Кандыбе так не повезло, он умер после допроса с пристрастием в гестапо.
В конце 1944 года немцы отпустили и Мельника, и Бандеру.
Мельник верно оценил политическую обстановку и геополитические расклады и после войны перебрался в тихий Люксембург. Первый послевоенный Великий Сбор мельниковцев избрал его пожизненным лидером ОУН.
Однако мельниковцы после войны сильно уступали в популярности бандеровцам и сосредоточились на эмигрантских вопросах.
Идеей-фикс Мельника стало объединение всех украинских эмигрантов. Уже после его смерти последователи Мельника частично реализовали эту идею, создав Всемирный конгресс украинцев. Сама ОУН(м) после смерти Мельника фактически слилась с рядом других эмигрантских организаций, в частности, с правительством УНР в изгнании.
Мельник умер в ноябре 1964 года в Люксембурге, не дожив полутора месяцев до своего 74-летия. Хотя он стоял у истоков организованного украинского национализма и долгие годы был либо одним из, либо полноправным лидером изначальных УВО и ОУН*, он вчистую проиграл Бандере битву за популярность.
* Организация, запрещенная в Российской Федерации
