Marine sponges are the single best source of potential anti-cancer drugs from the marine environment. This study was to search for novel chemotherapeutic compounds from marine sponges collected from the South Australia coastline. Non-polar extracts from twelve sponge species were screened for anti-cancer activity against five human cancer cell lines: colon cancer DLD-1, lung cancer A-549, breast cancer MCF-7, cervical cancer Hela, and prostate cancer DU-145. Ten out of twelve species tested showed anti-proliferative effect on all five cell lines tested, especially A-549, as detected by the Crystal Violet assay. The IC50 values ranged from 1.0 to 40 µg/ml. The anti-cancer activity induced by the sponge extracts was found to be associated with apoptosis induction and cell cycle arrest in G1 phase. To identify the active compounds, the most active extract from the sponge Acarnid sp. was selected for fractionation using n-hexane (F1), dichloromethane (F2), butanol (F3), 50% methanol (F4), and 100% methanol (F5). The cytotoxicity of each fraction was tested on the A-549 cell line. F2 and F3 were found to be active, with IC50 values of 0.5 and 5 µg/ml, respectively. Anti-invasive activity of F2 and F3 on A-549 cell line was investigated at non-toxic concentrations. F2 treatment (0.25 µg/ml) inhibited the abilities of motility (approximately 40%), migration (57%), and invasion (72%) of A-549 cells compared with the untreated control, as detected by the Wound Healing, Migration and Matrigel Invasion Boyden chamber assays. However, F3 did not show anti-invasive activity under the tested conditions. Taken together, the sponge extracts from South Australia Waters exhibit a broad spectrum of anti-cancer activities. These extracts are currently undergoing further analysis to identify the active constituents and to investigate the underlying anti-cancer mechanisms.