Als Sohn einer Lehrerfamilie studierte Müller katholische Theologie Geschichte und Philosophie in Berlin Tübingen wechselte allerdings zu Rechtswissenschaft und Staatswissenschaft promovierte darin. Es arbeitete von 1929 bis 1933 in der Verwaltung der Diözese Rottenburg . Schon vor 1933 schloss er sich Zentrum an. Ab 1934 war er Amtsgerichtsrat bzw. Landgerichtsrat in Württemberg .
Von den Besatzungsmächten wurde er als und schließlich als Ministerialdirektor des Justizministeriums eingesetzt. 1947 wurde er in Biberach an der Riß zum Landesvorsitzenden der CDU Württemberg-Hohenzollern gewählt darauf als Vertreter des Wahlkreises Tübingen zum des Landtages.
Am 13. August 1948 wurde er zum Staatspräsidenten von Württemberg-Hohenzollern gewählt. Dieses Amt hatte er bis inne. Namentlich im Demontagestreit von 1948/49 mit Franzosen der bis zum Frühjahr 1949 dauerte sich Gebhard Müller einen Namen.
Am 25. April 1952 wurde nicht Müller sondern Reinhold Maier (FDP/DVP) zum ersten Ministerpräsidenten des neuen gewählt weil - so der Historiker Klaus-Jürgen im Jahr 2000 - Gebhard Müller die des neu gegründeten Südweststaats noch nicht auf Linie bringen konnte.
Entsprechend seiner konservativen katholischen Prägung war Zeit seines Lebens ein Anhänger der Todesstrafe der Konfessionsschule die er als Tübinger Regierungschef Südwürttemberg als Preis für seine Zustimmung für Bildung des Südweststaats zu erhalten wusste bis von der Großen Koalition 1968 durch die Gemeinschaftsschule als Regelschule abgelöst wurde.
Gerhard Taddey (Hg.) Gebhard Müller - Leben für das Recht und die Politik. anläßlich seines 100. Geburtstages. Stuttgart: Kohlhammer 2000. der Kommission für geschichtliche Landeskunde in Baden-Württemberg. B. Forschungen Bd. 148)
Udo Rauch/Antje Zacharias (Hg.) Sieben Jahre 1945-1952 Tübingen und Württemberg-Hohenzollern. Tübingen 2002