Five new lyngbyabellin analogs along with a known compound, dolabellin, have been isolated from the marine cyanobacterium Lyngbya majuscula collected from Papua New Guinea. The structures of lyngbyabellins E–I were elucidated through extensive spectroscopic analysis, including HR-FABMS and 1D and 2D NMR experiments. The absolute configurations of lyngbyabellin E and H were ascertained by chiral HPLC and GC/MS analysis of degradation products, in combination with NMR experiments. All five lyngbyabellins showed cytotoxicity to NCI-H460 human lung tumor and neuro-2a mouse neuroblastoma cell lines with LC50 values between 0.2 and 4.8 mM.