Auf Grund seiner Flugerfahrung wurde Tolkowsky Gründungsmitglied der israelischen Luftwaffe. Er trat anfangs der Scherut Avir bei, dem kurzlebigen Vorläufer der IAF bzw. Luftstreitkraft der Hagana, wo er bei der Beschaffung moderner Militärmaschinen aus der Tschechoslowakei half. Im Jahr 1959 verließ er die Armee mit dem Rang Aluf (entspricht etwa einem Generalmajor).