Mel'nyk nacque vicino a Drohobyč, in Galizia, in una famiglia di contadini. Tra il 1912 e il 1914 studiò alla Scuola superiore di agricoltura di Vienna. Con lo scoppio della prima guerra mondiale, Mel'nyk prestò servizio come ufficiale dell'esercito austro-ungarico come volontario al comando di una compagnia di fucilieri Sich ucraini, dove venne soprannominato "Lord Mel'nyk" dai colleghi ufficiali ucraini e austriaci.[1] Fu fatto prigioniero dai russi nel 1916. Durante la prigionia Mel'nyk strinse un sodalizio con Jevhen Konovalec' e aderì al movimento nazionalista ucraino.
Durante la guerra sovietico-ucraina del 1917-1921 Mel'nyk sostenne Symon Petljura e fu promosso al grado di colonnello nell'esercito della Repubblica Popolare Ucraina. Insieme a Jevhen Konovalec' e molti altri fondò l'Organizzazione dei Nazionalisti Ucraini (OUN) nel 1929. Tra il 1924 e il 1928 Mel'nyk fu imprigionato per attività terroristiche dal governo polacco. Durante gli anni '30 si ritirò dalla politica[2] e lavorò come ingegnere e come direttore delle foreste nelle vaste proprietà del metropolita della Chiesa greco-cattolica ucrainaAndrej Szeptycki. Divenne poi presidente di Orlo, un'organizzazione giovanile cattolica galiziana considerata antinazionalista da molti membri dell'OUN.[1]
Dopo l'assassinio del leader dell'OUN Konovalec' nel 1938, gli esponenti di spicco dell'organizzazione all'estero chieseri a Mel'nyk di prendere le redini della stessa nel 1939.[2] Fu scelto in parte con la speranza di portare l'OUN su posizioni più moderate e pragmatiche, ma anche per il desiderio dell'organizzazione di riparare i legami tesi con la Chiesa cattolica.[1] Il gruppo che aveva scelto Mel'nyk come capo ammirava aspetti del fascismo di Benito Mussolini ma condannava il nazismo.[3] Nel 1940 una fazione più radicale dell'OUN, guidata da Stepan Bandera e con sede in Ucraina, si distaccò dalla parte guidata da Mel'nyk in esilio. Le due organizzazioni rivali divennero note come Melnykivci e Banderivci.
Dopo il 1938 Mel'nyk e Bandera furono reclutati nell'intelligence militare della Germania nazista Abwehr per condurre azioni di spionaggio, controspionaggio e sabotaggio.[4] L'obiettivo dell'Abwehr era quello di svolgere attività di diversione a seguito dell'attacco pianificato della Germania contro l'Unione Sovietica. A Mel'nyk fu dato il nome in codice "Console I". Queste informazioni fanno parte della testimonianza che il colonnello dell'Abwehr Erwin Stolze rese il 25 dicembre 1945 e che presentò al processo di Norimberga, chiedendone l'ammissione come prova.[5][6]
Dopo l'invasione tedesca dell'Unione Sovietica nel giugno 1941, Mel'nyk dichiarò indipendente il proprio governo ucraino a Rivne, in competizione con i sostenitori di Bandera per l'influenza nell'Ucraina occidentale. Inizialmente, i sostenitori più conservatori e moderati di Mel'nyk godevano del sostegno contro i radicali di Bandera sia dalla Chiesa greco-cattolica ucraina che dalle autorità militari tedesche. La sua riluttanza ad affermare il proprio dominio lo svantaggiò rispetto ai suoi rivali più giovani e violenti della fazione di Bandera.[1] Molti degli stretti collaboratori di Mel'nyk furono uccisi dall'Esercito insurrezionale ucraino (UPA) di Bandera tra il 1941 e il 1944 e il movimento di Bandera arrivò a dominare l'ambiente politico nazionalista ucraino nella maggior parte dell'Ucraina occidentale. Nel 1944 Mel'nyk fu brevemente imprigionato dalla Gestapo durante una repressione contro il movimento nazionalista ucraino.
Dopo la guerra, Mel'nyk fuggì in Occidente e visse in Lussemburgo, Germania Ovest e Canada. Rimase politicamente attivo e diresse una serie di organizzazioni di emigrati ucraini. Morì a Clervaux, in Lussemburgo, all'età di 73 anni, e fu sepolto nel cimitero di Bonnevoie, nella città di Lussemburgo.
Alla fine del 2006, l'amministrazione comunale di Leopoli annunciò il trasferimento delle tombe di Andrij Mel'nyk, Jevhen Konovalec', Stepan Bandera e altri leader chiave dell'OUN e dell'UPA in una nuova area del cimitero di Lychakiv specificamente dedicata alla lotta di liberazione nazionale ucraina.[7]
«Stolze's testimony of 25th December, 1945, which was given to Lieutenant-Colonel Burashnikov, of the Counter-Intelligence Service of the Red Army and which I submit to the Tribunal as Exhibit USSR 231 with the request that it be accepted as evidence. [...] 'In carrying out the above-mentioned instructions of Keitel and Jodl, I contacted Ukrainian Nationalists who were in the German Intelligence Service and other members of the Nationalist Fascist groups, whom I enlisted in to carry out the tasks as set out above. In particular, instructions were given by me personally to the leaders of the Ukrainian Nationalists, the German Agents Myelnik (code name 'Consul I') and Bandara to organise, immediately upon Germany's attack on the Soviet Union, and to provoke demonstrations in the Ukraine, in order to disrupt the immediate rear of the Soviet Armies, and also to convince international public opinion of alleged disintegration of the Soviet rear.'»
