Bioassay-guided fractionation of the organic extract of the Red Sea sponge Xestospongia testudinaria led to the isolation of 13 compounds including two new sterol esters, xestosterol palmitate (2) and xestosterol ester of l6'-bromo-(7'E,11'E,l5'E)-hexadeca-7',11',l5'-triene-5',13'-diynoic acid (4), together with eleven known compounds: xestosterol (1), xestosterol ester of 18'-bromooctadeca-7'E,9'E-diene-7',15'-diynoic acid (3), and the brominated acetylenic fatty acid derivatives, (5E,11E,15E,19E)-20-bromoeicosa-5,11,15,19-tetraene-9,17-diynoic acid (5), 18,18-dibromo-(9E)-octadeca-9,17-diene-5,7-diynoic acid (6), 18-bromooctadeca-(9E,17E)-diene-7,15-diynoic acid (7), 18-bromooctadeca-(9E,13E,17E)-triene-7,15-diynoic acid (8), l6-bromo (7E,11E,l5E)hexadeca-7,11,l5-triene-5,13-diynoic acid (9), 2-methylmaleimide-5-oxime (10), maleimide-5-oxime (11), tetillapyrone (12), and nortetillapyrone (13). The chemical structures of the isolated compounds were accomplished using one- and two-dimensional NMR, infrared and high-resolution electron impact mass spectroscopy (1D, 2D NMR, IR and HREIMS), and by comparison with the data of the known compounds. The total alcoholic and n-hexane extracts showed remarkable cytotoxic activity against human cervical cancer (HeLa), human hepatocellular carcinoma (HepG-2), and human medulloblastoma (Daoy) cancer cell lines. Interestingly, the dibrominated C18-acetylenic fatty acid (6) exhibited the most potent growth inhibitory activity against these cancer cell lines followed by Compounds 7 and 9. Apparently, the dibromination of the terminal olefinic moiety has an enhanced effect on the cytotoxic activity.