Powołany w 1915 roku do armii Austro-Węgier, przez kilka miesięcy brał udział w walkach na froncie wschodnim. Służył w szeregach 10, a następnie 60 pułku piechoty. Po powrocie z frontu zdał maturę w Cieszynie i wstąpił do szkoły oficerskiej. Starał się o przydział do jednostek lotniczych. Kostrzewski został skierowany do szkoły pilotów i następnie, w stopniu podporucznika pilota, został skierowany na front włoski. Do października 1918 roku służył w eskadrze myśliwskiej Flik 42/J. Na stopień chorążego został mianowany ze starszeństwem z 1 października 1916, a na stopień podporucznika ze starszeństwem z 1 lutego 1917 w korpusie oficerów rezerwy piechoty.
W listopadzie 1918 roku przebywał na urlopie w rodzinnym Przemyślu, gdzie zastał go upadek Austrii i wybuch wojny polsko-ukraińskiej. Kostrzewski zgłosił się do Wojska Polskiego. Został mianowany komendantem lotniska w Hureczku, które z niewielką grupą żołnierzy bronił przed atakami Ukraińców. Wkrótce cały sprzęt lotniczy przewiózł do Krakowa. Od stycznia 1919 roku Kostrzewski przydzielony został do 7 Eskadry Lotniczej wchodzącej w skład III Grupy Lotniczej. Odbył liczne loty bojowe z lotniska Lewandówka we Lwowie.