W tym czasie udał się do getta wileńskiego, gdzie nawiązał kontakty z przywódcami Farejnikte Partizaner-Organizacje. Ostatecznie wiosną 1943 jego grupa dołączyła do radzieckiej partyzantki.
Rudnicki służył początkowo w oddziale im. Czapajewa, wchodzącym w skład partyzanckiej brygady im. Woroszyłowa, którą dowodził Fiodor Markow. Później dołączył do oddziału „Żalgiris” złożonego z przerzuconych zza linii frontu litewskich komunistów (gdy ten został przekształcony w brygadę, znalazł się w składzie oddziału „Vilnius”). Jednostki te operowały w lasach wokół jeziora Narocz oraz na obszarze pomiędzy Kozianami i Hoduciszkami. W ich szeregach 1943–1944 walczył z Niemcami i ich kolaborantami, uczestnicząc m.in. w akcjach wymierzonych w transport kolejowy. Na rozkaz dowództwa przyjął konspiracyjne nazwisko „Anatolij Kunicki”; w ten sposób narodził się jego partyzancki pseudonim „Tolka” (zdrobnienie imienia Anatolij), którego używał także po wojnie. W autobiografii twierdził, że musiał sobie radzić z antysemityzmem towarzyszy z brygady Markowa. Za walkę w partyzantce został odznaczony medalem „Partyzantowi Wojny Ojczyźnianej” pierwszej klasy.