Sachverhalt: A. Die Erben des G.X._, R.X._ und H.X._ (Kläger), vermieteten der Garage A._ AG (Beklagte) Räumlichkeiten im Erdgeschoss, im Keller und in der Hofunterkellerung der Liegenschaften B._strasse .... in Zürich zur Benützung als Autogarage, Autoreparaturwerkstätte, Auto-Einstellhalle und Büro. Das Mietverhältnis geht auf einen zwischen G.X._ und der Rechtsvorgängerin der Beklagten per 1. Januar 1978 abgeschlossenen Mietvertrag zurück. Am 22. Juni 1999 verlangte die Beklagte eine Mietzinsherabsetzung, die sie mit dem gesunkenen Hypothekarzinsfuss begründete. Die Kläger entsprachen diesem Begehren per 1. April 2000. Am 25. Februar 1999 orientierten die Kläger die Beklagte über eine anstehende Renovation an der Liegenschaft B._strasse ..... Die der Beklagten dadurch entstandenen Unannehmlichkeiten und die deswegen von der Beklagten geltend gemachten Schadenersatzansprüche wurden in der Folge verschiedentlich mündlich und schriftlich thematisiert. Im Februar 2000 übermittelte die Beklagte den Klägern eine Liste sämtlicher umbaubedingter Störungen vom 26. Oktober 1999 bis zum 18. Februar 2000. Am 9. März 2000 trafen sich die Parteien zu einer Besprechung, über welche R.X._ ein Protokoll erstellte. Danach vereinbarten die Parteien, dass die Kläger der Beklagten für die verschiedenen renovationsbedingten Störungen, Blockaden, Ausfälle und Umtriebe insgesamt Fr. 2'150.-- bezahlen würde. Ausserdem kamen sie überein, dass die Beklagte die Reparatur der Schäden des Sturms Lothar in Auftrag geben würde und dass sie anschliessend die Entschädigung der Gebäudeversicherung im Betrag von maximal Fr. 10'500.-- erhalten werde. Der Betrag von Fr. 2'150.-- wurde am 11. April 2000 beglichen. Wegen weiterer Betriebsbeeinträchtigungen aufgrund der Umbauten in der Zeit nach dem 9. März 2000 wurden im August 2000 im Einverständnis mit den Klägern Fr. 2'500.-- von den Mietzinsen und Nebenkosten in Abzug gebracht. B. Die Kläger kündigten das Mietverhältnis mit amtlichem Formular vom 26. Oktober 2001 auf den 30. September 2002 wegen Nutzungsänderung im Rahmen geänderter Vermietungsstruktur. Hierauf stellte die Beklagte am 21. November 2001 der Schlichtungsbehörde den Antrag, die Kündigung für ungültig zu erklären, dem die Schlichtungsbehörde mit Beschluss vom 8. Februar 2002 entsprach. Das Eventualbegehren der Beklagten um eine längst mögliche Erstreckung des Mietverhältnisses wurde damit gegenstandslos. Das Mietgericht des Bezirks Zürich erklärte jedoch am 9. Oktober 2003 in Gutheissung der Klage die Kündigung vom 26. Oktober 2001 auf den 30. September 2002 für gültig, und es erstreckte das Mietverhältnis erstmals bis und mit 30. September 2004. Das Obergericht des Kantons Zürich, II. Zivilkammer, wies die hiegegen erhobene Berufung der Beklagten ab und bestätigte das Urteil des Bezirksgerichts mit Beschluss vom 19. Februar 2004. C. Die Beklagte beantragt dem Bundesgericht mit eidgenössischer Berufung, in Aufhebung des obergerichtlichen Beschlusses die Kündigung für ungültig zu erklären. Die Kläger schliessen auf kostenfällige Abweisung der Berufung. 