Prawdopodobnie w 1904 r. został członkiem dzielnicy praskiej Polskiej Partii Socjalistycznej, przyjmując pseudonim „Witold”. Do pracy w PPS wciągnął go między innymi Józef Elżanowski, nauczyciel dyrektor praskiego gimnazjum. W tym czasie uczestniczył w zajęciach kół edukacyjnych. Zajęcia polityczne prowadzili Józef Kwiatek, Antoni Brzozowski, zajęcia z przyrody Wiesław Malinowski, z historii Jan Cynarski. W swoich wspomnieniach Jan Cynarski wskazywał Okrzeję jako najbardziej wyróżniającego się podopiecznego. – Z inicjatywy Bolesława Bergera „Kuroki”, został również członkiem nowo powstających grup bojowych PPS – Kół Bojowych Samoobrony Robotniczej, zwanych również „oddziałami technicznymi”, których zadaniem było rozklejanie odezw, dostarczanie do fabryk „bibuły”, urządzanie drobnych demonstracji, bicie kijami zanadto natrętnych szpicli.

W obronie Marcina Kasprzaka 2 sierpnia 1904 Warszawski Komitet Robotniczy PPS podjął akcję w obronie aresztowanego Marcina Kasprzaka. 3 sierpnia 1904 odbyła się demonstracja PPS w Alejach Ujazdowskich. Stefan Okrzeja wzniósł czerwony sztandar z napisem „Precz z sądami wojennymi – PPS”. Znajdująca się w pogotowiu policja zaatakowała i rozbiła demonstrantów. Okrzeja zdołał zwinąć sztandar i uciec.