From 1993 to 1996, Fritz was head coach at Blinn College. He turned around a program that had gone 5-24-1 in its three previous seasons, producing a 39-5-1 record. Willie Fritz lead the team to two national junior college championships, in 1994 and 1996. For his efforts at Blinn, Fritz has been inducted into the NJCAA Hall of Fame.
Willie Fritz coached at the University of Central Missouri from 1997 until 2009, leading the Mules to their first post-season berth in 32 years when they defeated Minnesota-Duluth in the 2001 Mineral Water Bowl. In 2002, Central Missouri earned its first NCAA Division II playoff berth after winning the Mid-America Athletic Association (MIAA) championship. Fritz became the university's "winningest" coach with a 97-47 record.
Fritz was the second member of his family to coach at Central Missouri. His father, the late Harry Fritz, was the Mules' head football coach in 1952 and later became executive director of the National Association of Intercollegiate Athletics (NAIA).
Willie Fritz became the 14th head football coach at Sam Houston State University on December 18, 2010. During the 2011 season, his second year at Sam Houston State University, Fritz coached the Bearkats to the FCS's only undefeated regular season and into the FCS playoffs. He coached the Bearkats to back-to-back national title game appearances in 2011 and 2012 in only three years of being head coach at Sam Houston State.
On January 10, 2014, Fritz became the head football coach at Georgia Southern University.
Before his coaching career, Fritz served as a graduate assistant for the Bearkat squads that went 16-6 in 1984-85 and won the 1985 Gulf Star Conference championship. He went on to become the secondary and special teams coach for the Bearkats in 1991 and 1992, helping lead Sam Houston to a Southland Conference championship.