The red alga Ptilonia australasica is endemic to Australian temperate waters. Chemical investigation of P. australasica led to the identification of four new polybrominated compounds, ptilones A-C (1-3) and australasol A (4). Their planar structures were established by extensive NMR and MS analyses. The low H/C ratio and the presence of a large number of heteroatoms made the structure elucidation challenging. The absolute configurations of 1, 2, and 4 were determined by quantum chemical ECD calculations employing time-dependent density functional theory. Ptilones A-C (1-3) show unique 4-ethyl-5-methylenecyclopent-2-enone (1 and 2) and 2-methyl-6-vinyl-4H-pyran-4-one (3) skeletons not previously reported in algal metabolites. Ptilone A displayed the most potent cytotoxicity against the human prostate cancer PC3 cells with an IC50 value of 0.44 μM and induced the PC3 cell cycle arrest in the G0/G1 phase.