Latem 1924 roku, na skutek zabiegów jego ojca, władze zgodziły się warunkowo zwolnić skazanego z odbywania ostatnich trzynastu miesięcy kary – pod warunkiem, że przez cały ten czas będzie przebywać poza granicami Polski.

Z dokumentów byłych sowieckich służb specjalnych wynika, że Fedak był przez pewien czas tajnym współpracownikiem NKWD, posługującym się pseudonimem „Bohun”. W latach 1939–1940 miał przebywać w Moskwie, gdzie „był wzywany do organów MSW”.

Następnie związał się z OUN-M. Po rozpoczęciu wojny niemiecko-sowieckiej towarzysząc wojskom niemieckim znalazł się we Lwowie, a następnie w Kijowie. Uczestniczył w śledztwie w sprawie śmierci Omelana Senyka i Mykoły Sciborskiego, liderów OUN-M, których 30 sierpnia 1941 roku zabito w zamachu w Żytomierzu. Podczas masowych egzekucji w Babim Jarze (29–30 września 1941) był tłumaczem Sonderkommando 4a, jednostki odpowiedzialnej za przeprowadzenie masakry kijowskich Żydów.