If no oxygen, then no mitochondria, which means no ATP, which means (except for rare exceptions) no multicellular organisms. Even animals that don’t use mitochondria use oxygen in other ways.
Except… biologists just discovered some critters don’t need oxygen. Ever. Multicellular organisms that don’t use oxygen have been reported, with eggs, even!
Deep under the Mediterranean Sea, in the mud beneath water full of salt and sulphur — and devoid of oxygen — multicelled creatures were found by researchers from the Polytechnic University of Marche, Ancona, Italy. They report their findings in the the open access journal BMC Biology.
Want to dig deeper?
Here’s a link to the abstract, from which you can get the full journal paper: The first metazoa living in permanently anoxic conditions by Roberto Danovaro, et al., BMC Biology 2010, 8:30 doi:10.1186/1741-7007-8-30