A new dimeric sesquiterpenoid with two eudesmane skeletons through a urea linkage, halichonadin A (1), as well as three new eudesmane sesquiterpenoids having a carbamate, an isonitrile, or an amino functionality, halichonadins B (2), C (3), and D (4), respectively, have been isolated from a marine sponge Halichondria sp., and the gross structures and relative stereochemistry of 1–4 were elucidated on the basis of spectral data and chemical means.