Mike Leach was fired as head coach for Texas Tech despite 10 consecutive winning seasons, 5 bowl game victories, and being named Big 12 Coach of the Year for 2008, the year before he was fired. His overall record at Tech was 84-43.
The general feeling around town seems to be that Tech fired Leach in order to avoid paying him an $800K bonus and additional $1.7M that his contract mandated for the coming season, using the “Adam James incident” as a pretense. There’s a book about the whole thing.