W lutym 1986 roku nowojorska gazeta The Village Voice w artykule zatytułowanym „To Catch a Nazi” zarzuciła CIA, że sprowadziło Łebedia do USA pod przybranym nazwiskiem i ukryło przed INS jego przeszłość jako nazistowskiego kolaboranta. Według gazety przeszedł on kurs w „szkole Gestapo” w Zakopanem, gdzie m.in. miał, wspólnie z Hansem Krügerem i jeszcze jednym Niemcem, maltretować Żyda podczas nauki wymuszania zeznań. Artykuł odbił się szerokim echem (publikacje m.in. w New York Post, New York Times, The Herald Statesman i prasie żydowskiej), a także wywołał obronę Łebedia w prasie ukraińskiej diaspory. 14 marca 1986 Łebed’ w liście do zaprzeczył, że „był nazistą”, czy też że kolaborował z Niemcami (w tym że był szkolony w jakiejkolwiek niemieckiej szkole policyjnej) i że prześladował Żydów lub przedstawicieli innych narodów. Przedstawił siebie jako bojownika o niepodległość Ukrainy, który walczył także z nazistowskimi Niemcami. W liście do The Village Voice (którego gazeta nie opublikowała) Łebed’ poprzez swojego prawnika przyznał, że „był na obozie w Zakopanem” od grudnia 1939 do stycznia 1940, gdzie było także dwóch funkcjonariuszy Sicherheitsdienst, w tym Hans Krüger, którzy mieli „nie wtrącać się w codzienne życie obozu”.