W Lublinie Krylenko w 1895 rozpoczął naukę w gimnazjum klasycznym, które ukończył w 1903 i jesienią tego roku wstąpił na wydział historyczno-filozoficzny Uniwersytetu Petersburskiego. Uczestniczył w zebraniach studenckich i demonstracjach ulicznych. W grudniu 1904 wstąpił do Socjaldemokratycznej Partii Robotniczej Rosji (SDPRR). Ukończył studia na wydziale historyczno-filozoficznym Uniwersytetu w Petersburgu w 1909 i na wydziale prawnym Uniwersytetu Charkowskiego w 1914. Uczestnik rewolucji 1905–1907. Przez krótki okres pracował jako nauczyciel języka rosyjskiego, literatury i historii Rosji w prywatnych szkołach w Sosnowcu i Lublinie. Podczas pobytu na ziemiach polskich nauczył się biegle władać językiem polskim, był też znanym polonofilem. Działalność polityczną prowadził w Petersburgu i Moskwie. Od 1906 członek organizacji wojskowej petersburskiego Komitetu Socjaldemokratycznej Partii Robotniczej Rosji (SDPRR). Od 1911 pracował jako redaktor w gazecie „Gwiazda” (Zwiezda), od 1913 w Prawdzie, a wcześniej, podczas pobytu w Lublinie pisywał do „Kuriera Lubelskiego”. Latem 1914 emigrował do Szwajcarii, gdzie uczestniczył w Konferencji Przedstawicieli Zagranicznych SDPRR w Bernie.