Brakowało mu funduszy na dotarcie do Petersburga, więc podjął pracę lekarza w armii rosyjskiej, która akurat stacjonowała w Gdańsku z powodu wojny o sukcesję polską. Stamtąd Steller udał się na pokładzie statku szpitalnego do Sankt Petersburga. Podczas rejsu zmienił swoje oryginalne nazwisko Stöller na Steller, gdyż w tej formie było lepiej wymawiane przez Rosjan.
Prawie bez pieniędzy dotarł w 1734 roku do rosyjskiej stolicy. W ogrodzie botanicznym Sankt Petersburga poznał prawosławnego arcybiskupa Teofana Prokopowicza, który został jego protektorem i wprowadził w krąg wykształconych mieszkańców miasta. W 1737 roku został mianowany adiunktem nauk przyrodniczych w Petersburskiej Akademii Nauk Przyrodniczych. Jeszcze w tym samym roku został członkiem Wielkiej Ekspedycji Północnej na Kamczatkę. Jego przełożonym został Johann Georg Gmelin. Tuż przed wyruszeniem z Sankt Petersburga poślubił wdowę po niemieckim badaczu Syberii Messerschmidcie. Ten związek długo nie przetrwał, już podczas podróży na Syberię – w Moskwie – para rozstała się. Po trudach podróży i bieżących studiach w wielu dziedzinach, m.in.