Chemical investigation of a new species of the deep-water marine sponge Leiodermatium, collected by manned submersible at a depth of 740 feet in Palau, resulted in the isolation of two cytotoxic macrolides, leiodolides A (1) and B (2). The leiodolides represent the first members of a new class of 19-membered ring macrolides, incorporating several unique functional groups including a conjugated oxazole ring, a bromine substituent, and an alpha-hydroxy-alpha-methyl carboxylic acid side-chain terminus. The structures of these new metabolites were established by spectroscopic analysis, chemical modification, and degradation. The relative and absolute stereochemistries at most chiral centers were assigned on detailed interpretation of spectroscopic data, coupled with chemical degradation and application of the modified Mosher ester method. Leiodolide A showed significant cytotoxicity (average GI(50) = 2.0 microM) in the National Cancer Institute's 60 cell line panel with enhanced activity against HL-60 leukemia and OVCAR-3 ovarian cancer cell lines.