1940 in Frankfurt/Main geboren. Studium der Germanistik, Musikwissenschaft und Philosophie in Frankfurt/Main. Von 1959 bis 1966 belegte er regelmäßig die Ferienkurse für Neue Musik in Darmstadt.
Ein erstes Engagement als Dramaturg erhielt Klaus Zehelein 1967 an den Bühnen der Landeshauptstadt Kiel. 1970 wechselte er von dort als Chefdramaturg an das Staatstheater Oldenburg (bis 1977) und übernahm zudem eine Lehrtätigkeit als Dozent für Musiksoziologie an der Universität Oldenburg. 1977 kam Klaus Zehelein als Chefdramaturg an die Städtischen Bühnen Frankfurt/Main und avancierte hier später zum koordinierten Operndirektor. Nebenher blieb Klaus Zehelein in der akademischen Lehre als Dozent an der State University of Minnesota sowie am Collège International de Philosophie in Paris engagiert. Gastprofessuren führten ihn an die Universität Gießen (Institut für angewandte Theaterwissenschaft) und 1986 bis 1992 an die Hochschule für angewandte Kunst in Wien. Nach einer zweijährigen Tätigkeit als freier Schauspiel- und Operndramaturg in Berlin, Frankfurt, Brüssel und Wien wurde Klaus Zehelein 1989 Künstlerischer Direktor des Hamburger Thalia Theaters. Von 1991 bis 2006 war er Opernintendant in Stuttgart und seit Mai 2003 auch Präsident des Deutschen Bühnenvereins. Seit Herbst 2006 ist Zehelein Präsident der Bayerischen Theaterakademie in München.
Für die Dramaturgie an der Oper Frankfurt wurde Klaus Zehelein 1983 mit dem Deutschen Kritikerpreis ausgezeichnet. Unter seiner Leitung ist die Staatsoper Stuttgart 1994, 1998, 1999, 2000, 2002 und 2006 in der Kritikerumfrage der Zeitschrift Opernwelt zum „Opernhaus des Jahres“ gewählt worden. Für besondere Verdienste um das Land Baden-Württemberg verlieh Ministerpräsident Erwin Teufel ihm im Jahr 2001 die Verdienstmedaille des Landes und im September 2003 den Titel Professor.