Born in Galicia, Hrytsai graduated from gymnasium in Drohobych (then part of eastern Poland) and became a member of the Ukrainian Military Organization (UVO).
In 1939 he was again incarcerated at Bereza Kartuska, but was released after Poland had been overrun by Germany and the Soviet Union.
From 1941 he headed the OUN's Military Staff, working to discover the German command's tactical plans, creating weapons and supply depots, and training officer cadres for a Ukrainian army.
In 1943 Hrytsai was arrested by the German Gestapo, but was freed by a Ukrainian Insurgent Army (UPA) attack on the prison.
In 1945 together with OUN Directorate member Taras Maivski, while carrying out assignments for the Ukrainian Chief Council of Liberation, he fell into a Czech police trap while crossing the Czech-German border.