The novel cyclic depsipeptides papuamides A (1), B (2), C (3), and D (4) have been isolated from Papua New Guinea collections of the sponges Theonella mirabilis and Theonella swinhoei. Their structures were determined by a combination of spectroscopic analysis and chemical degradation and derivatization studies. In addition to glycine, alanine, and threonine, these peptides contain a number of unusual amino acids including 3,4-dimethylglutamine, beta-methoxytyrosine, 3-methoxyalanine, and 2,3-diaminobutanoic acid or 2-amino-2-butenoic acid residues. Papuamides A-D (1-4) are also the first marine-derived peptides reported to contain 3-hydroxyleucine and homoproline residues. These peptides also contain a previously undescribed 2,3-dihydroxy-2,6,8-trimethyldeca-(4Z,6E)-dienoic acid moiety N-linked to a terminal glycine residue. Papuamides A (1) and B (2) inhibited the infection of human T-lymphoblastoid cells by HIV-1(RF) in vitro with an EC50 of approximately 4 ng/mL. Compound 1 was also cytotoxic against a panel of human cancer cell lines with a mean IC50 of 75 ng/mL.