Er wurde am 21. September 1927 an Wien als Sohn des Beamten und Schriftstellers Eduard Kehlmann geboren. Sowohl sein Vater als auch seine Mutter waren getaufte Juden. Durch Dokumentenfälschung – Originaldokumente wurden bei einem Archivbrand vernichtet, wodurch neue Dokumente ausgestellt werden mussten – deklarierten sich Michael Kehlmanns Eltern als sogenannte „Halbjuden“, um die Nazi-Zeit besser zu überstehen. Aufgrund seiner Widerstandstätigkeit wurde er 1944 bei einem abendlichen Treffen verhaftet und in ein Nebenlager des KZ Mauthausen, dem Lager Maria Lanzendorf, gebracht.
Er absolvierte 1945 die Matura und studierte anschließend an der Universität Wien Germanistik und Philosophie. 1950 begann er zusammen mit Helmut Qualtinger und Carl Merz, im von ihm geleiteten „Kleinen Theater im Konzerthaus“ Kabarett zu spielen. Daraus entstand die heute als „Namenloses Ensemble“ bekannte Kabarettgruppe, zu der dann später Gerhard Bronner, Peter Wehle, Georg Kreisler, Louise Martini und viele andere Mitglieder stießen. Von 1950 bis 1953 leitete er das „Kleine Theater im Konzerthaus“ und inszenierte an den verschiedensten Häusern in Österreich, Deutschland und der Schweiz, am Theater in der Josefstadt und am Wiener Burgtheater.
Michael Kehlmann verließ 1953 Wien und ging zum NDR als Fernsehregisseur. Für über 100 Fernsehfilme zeichnete er sich im Laufe seines Schaffens verantwortlich. Seine zweiteilige Verfilmung von Joseph Roths Roman "Radetzkymarsch" aus dem Jahr 1965 wurde zu einem internationalen Erfolg. Er drehte auch eine Reihe von Spielfilmen, darunter „Kurzer Prozess“ mit Helmut Qualtinger (1967) und „Nichts als Erinnerung“ mit Paula Wessely in der Hauptrolle (1973).
Michael Kehlmann war der Vater des Autors Daniel Kehlmann („Die Vermessung der Welt“).
Er verstarb am 1. Dezember 2005 in Wien.