Stiehm began his coaching career at Ripon College in 1910, where he led the Red Hawks football team to a 4–3 record. From 1911 to 1915, he coached football at Nebraska, and compiled an 35–2–3 record. From 1913 to 1915, his teams went undefeated seasons. In the history of the Nebraska Cornhuskers football program, Stiehm has the highest winning percentage (.913) of anyone who coached more than two games. From 1916 to 1921, he coached at Indiana, and compiled a 20–18–1 record.
National champion Postseason invitational champion Conference regular season champion Conference regular season and conference tournament champion Division regular season champion Division regular season and conference tournament champion Conference tournament champion