Stainhaus studiò matematica all'Università di Leopoli e di Gottinga, dove conseguì nel 1919 il dottorato di ricerca con la tesi Neue Anwendungen des Dirichlet'schen Prinzips (Nuove applicazioni del principio di Dirichlet).
Nel 1917 ottenne l'autorizzazione all'insegnamento a Leopoli e nel 1918 pubblicò il notevole articolo Additive und stetige Funktionaloperationen. Nel 1920 divenne professore all'università di Leopoli.