W Konstantynopolu już od czasu klęski Powstania Listopadowego w 1831 r. formowane były polskie oddziały ochotnicze. To tam na rzecz sprawy polskiej działał Sadyk Pasza (Michał Czajkowski (1804–1886) i tam w trakcie misji tworzenia legionów polskich zmarł Adam Mickiewicz (1798–1855). Ruch ten przybierał na sile i ściągał coraz większe rzesze emigrantów polskich.

Andriolli dotarł do Konstantynopola w 1865 r., a następnie wraz z Tomaszem Gregutowiczem wyruszył na Podole w celu poszukiwania ochotników do legionów. Zdradzeni przez przewodnika, Andriolli i jego towarzysz zostali uwięzieni w twierdzy chocimskiej. Więźniowie wyłamali w nocy kratę w oknie i na linie zrobionej z prześcieradeł wydostali się z celi. Gregutowiczowi udało się uciec, Andriollego niestety złapano, skatowano i wysłano do Wilna. Tam w 1868 r. sąd wojenny wydał wyrok, w którym został on oskarżony o zbrojny udział w powstaniu, pełnienie obowiązków komisarza władz rewolucyjnych na gubernię kowieńską, wreszcie przedzieranie się nielegalnie do kraju w roli emisariusza. Postanowiono przestępcę politycznego Elwira Andriolli pozbawić wszelkich praw i wysłać na roboty katorżne na przeciąg 15 lat. Od tego wyroku uratowało go wstawiennictwo żony gubernatora wileńskiego. Andriolli zyskał jej  przychylność za sprawą pochlebnego portretu, który udało mu się namalować i wysłać. Nie uchroniło go to od kary, ale wyrok znacznie złagodzono, zamieniając go na zesłanie do Wiatki (obecnego Kirowa), w europejskiej części Rosji.

Dotarł tam pod eskortą we wrześniu 1868 roku. Objęto go wprawdzie nadzorem policyjnym, ale mógł funkcjonować względnie normalnie. Zarabiał na życie, sprzedając ogromne ilości małych tanich rysunków. Po zdobyciu popularności zaczął malować portrety miejscowych znakomitości, które przynosiły mu pokaźne dochody. Udzielał także lekcji rysunków. Jego uczennicą była m.in. Anna Bilińska (1854–1893), która została znaną portrecistką. W Wiatce Andriolli został polecony wpływowemu duchownemu prawosławnemu (archirejowi) Apollsowi przez przebywającego na zesłaniu biskupa wileńskiego Adama Stanisława Krasińskiego (1810–1891). Dzięki tym rekomendacjom, po sprawdzeniu jego umiejętności, zaczął otrzymywać dobrze płatne zlecenia. Odnowił prawie wszystkie cerkwie w regionie, namalował wiele ikon. Dał się tam poznać jako niezwykły człowiek, bywały w świecie, towarzyski i nadzwyczaj pracowity. Zdobył tyle zamówień, że nie zdążył ich zrealizować w czasie pobytu, skróconego amnestią z okazji urodzin Wielkiego Księcia Jurija Aleksandrowicza, ogłoszoną 12 maja 1871 r.

Wrócił do Wiatki na kilka miesięcy latem 1872 r. już jako wolny człowiek, aby namalować szereg dużych religijnych obrazów, zamówionych wcześniej przez cerkwie.