Sachverhalt: Sachverhalt: A. Der Zweckverband A._ ist Träger des Alterszentrums "B._". Am 31. März 2003 kündigte die Heimkommission das Arbeitsverhältnis des seit 1. Februar 1990 als Verwaltungsleiter des Zentrums amtenden X._ per 30. September 2003 und stellte diesen sofort frei. A. Der Zweckverband A._ ist Träger des Alterszentrums "B._". Am 31. März 2003 kündigte die Heimkommission das Arbeitsverhältnis des seit 1. Februar 1990 als Verwaltungsleiter des Zentrums amtenden X._ per 30. September 2003 und stellte diesen sofort frei. B. X._ rekurrierte am 25. April 2003 an den Bezirksrat Winterthur mit dem Antrag, die Unwirksamkeit der Kündigung festzustellen. Mit Beschluss vom 21. November 2003 wies der Bezirksrat Winterthur den Rekurs ab. Auf die in der Replik erhobene Aufsichtsbeschwerde X._s trat er nicht ein. B. X._ rekurrierte am 25. April 2003 an den Bezirksrat Winterthur mit dem Antrag, die Unwirksamkeit der Kündigung festzustellen. Mit Beschluss vom 21. November 2003 wies der Bezirksrat Winterthur den Rekurs ab. Auf die in der Replik erhobene Aufsichtsbeschwerde X._s trat er nicht ein. C. Mit Eingabe vom 6. Februar 2004 erhob X._ Beschwerde beim Verwaltungsgericht des Kantons Zürich. Er verlangte die Feststellung, dass die Kündigung unwirksam, eventuell sachlich nicht gerechtfertigt sei. Subeventuell beantragte er, die Angelegenheit zur vollständigen Feststellung des Sachverhalts und anschliessender neuer Entscheidung an den Bezirksrat zurückzuweisen. Das Verwaltungsgericht Zürich trat mit Beschluss vom 12. Mai 2004 auf die Beschwerde nicht ein. Es auferlegte X._ die Kosten und verpflichtete ihn, dem Zweckverband A._ eine Parteientschädigung von Fr. 2'000.-- auszurichten. C. Mit Eingabe vom 6. Februar 2004 erhob X._ Beschwerde beim Verwaltungsgericht des Kantons Zürich. Er verlangte die Feststellung, dass die Kündigung unwirksam, eventuell sachlich nicht gerechtfertigt sei. Subeventuell beantragte er, die Angelegenheit zur vollständigen Feststellung des Sachverhalts und anschliessender neuer Entscheidung an den Bezirksrat zurückzuweisen. Das Verwaltungsgericht Zürich trat mit Beschluss vom 12. Mai 2004 auf die Beschwerde nicht ein. Es auferlegte X._ die Kosten und verpflichtete ihn, dem Zweckverband A._ eine Parteientschädigung von Fr. 2'000.-- auszurichten. D. Mit staatsrechtlicher Beschwerde wegen Verletzung von Art. 9 und 29 Abs. 1 BV beantragt X._, den Entscheid des Verwaltungsgerichts des Kantons Zürich vom 12. Mai 2004 aufzuheben und das Verwaltungsgericht anzuweisen, auf die Beschwerde einzutreten. D. Mit staatsrechtlicher Beschwerde wegen Verletzung von Art. 9 und 29 Abs. 1 BV beantragt X._, den Entscheid des Verwaltungsgerichts des Kantons Zürich vom 12. Mai 2004 aufzuheben und das Verwaltungsgericht anzuweisen, auf die Beschwerde einzutreten. E. Der Zweckverband A._ schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei.