W 1903, podczas pobytu w Szwajcarii, Taratuta związała się z ruchem anarchokomunistycznym. W 1904 wróciła do Odessy i dołączyła do grupy Neprimirimych (ros. непримиримых), która swoją ideologią nawiązywała do myśli Jana Wacława Machajskiego. Taratuta została aresztowana w kwietniu 1904, ale uwolniono ją kilka miesięcy później z powodu braku dowodów. Po zwolnieniu dołączyła do Odessańskiej Grupy Robotników Anarchokomunistów. Zaczęła stawać się coraz bardziej znaną osobą wśród rosyjskiego ruchu anarchistycznego.
Taratuta została ponownie zatrzymana w październiku 1905, ale zwolniono ją podczas amnestii politycznej, która była wynikiem rewolucji. Dołączyła do bojowego skrzydła Południoworosyjskiej Grupy Anarchokomunistów, która stosowała „terror bez motywacji” - ogólne ataki na instytucje i przedstawicieli burżuazji, a nie na konkretne osoby. Taratuta była zamieszana w atak bombowy na Café Libman w Odessie w grudniu 1905, za co skazano ją na 17 lat więzienia.
Uciekła z więzienia w grudniu 1906 i wyjechała do Genewy, gdzie dołączyła do Buntar ("Buntownicy") i redagowała gazetę, zwaną także Buntar.