Stram debuttò come allenatore con i Dallas Texans di Lamar Hunt della neonata American Football League nel 1960. Nel 1962 vinse il suo primo campionato AFL battendo in finale gli Houston Oilers per 20-17. Nel 1966 la franchigia si trasferì diventando i Kansas City Chiefs. La squadra vinse un altro campionato NFL nel 1966 contro i Buffalo Bills potendo contare su una delle migliori difese della storia del football professionistico, comprendente tre futuri Hall of Famer e otto All-Star. I Chiefs giocarono contro i Green Bay Packers nel Super Bowl I ma furono sconfitti 35–10.
I Kansas City Chiefs vinsero il loro terzo campionato AFL con Stram alla loro guida nel 1969. Nel Super Bowl IV, essi dominarono i Minnesota Vikings sia in attacco che in difesa[1], con Stram che in quella gara divenne il primo allenatore di football ad indossare un microfono. Stram rimase coi Chiefs fino alla stagione 1974. Nel 1976 e 1977, Stram allenò i New Orleans Saints ma, anche a causa degli infortuni della loro stella, il quarterbackArchie Manning, terminò le due stagioni con record di 4-10 e 3-11. Dopo il ritiro da allenatore divenne un commentatore di successo per la CBS.
Stram detiene il maggior numero di vittorie da allenatore (87), apparizioni ai playoff (6) e miglior record nei playoff della storia della AFL (5–1).
