Po krótkim pobycie w więzieniu w Warszawie został ponownie skazany na osiedlenie administracyjne w Jarosławiu.

W Jarosławiu Kalajew został przez Borisa Sawinkowa i Aleksego Remizowa, działaczy partii eserowskiej, ostatecznie przekonany co do słuszności taktyki terroru indywidualnego. Spotkał się z Jewno Azefem, przywódcą organizacji bojowej eserowców, i zadeklarował swoją chęć do czynnego uczestnictwa w zabójstwach politycznych. Współorganizował zamach na ministra spraw wewnętrznych Wiaczesława Plehwego, po czym zgodził się zostać bezpośrednim wykonawcą zamachu na wielkiego księcia Sergiusza Aleksandrowicza Romanowa, generała gubernatora Moskwy, stryja cara Mikołaja II Romanowa. Zamach został wyznaczony na 15 lutego 1905, gdy książę miał udać się do Teatru Bolszoj. Kalajew, uzbrojony w bombę domowej produkcji, oczekiwał przed teatrem, jednak zrezygnował z dokonania zamachu, gdy ujrzał w karecie wielkiego księcia również jego żonę, wielką księżnę Elżbietę oraz ich dwoje adoptowanych dzieci. Kalajew zobowiązał się jednak do powtórzenia zamachu w dwa dni później, o ile wielki książę będzie w powozie sam. Tym razem do zamachu doszło;