Born to a middle class Jewish family in Vienna, Zeisl was the son of Kamilla (Feitler) and Siegmund Zeisl. His musical precocity enabled him to gain a place at the Vienna State Academy (against the wishes of his family) when he was 14, at which age his first song was published. While there, he studied with Richard Stöhr, Joseph Marx and Hugo Kauder. He won a state prize for a setting of the Requiem mass in 1934, but his Jewish background made it difficult to obtain work and publication. After the Anschluss in 1938 he fled, first to Paris, where he began work on an opera based on Joseph Roth's Job, and then to New York City.