Seven new nitrile-bearing polyacetylenes, named albanitriles A-G, were isolated from a marine sponge of the Mycale genus (Order: Poecilosclerida, Family: Mycalidae) collected near Albany, Western Australia. Structural elucidation was achieved using a combination of high-resolution mass spectrometry and ultraviolet/visible, infrared, and nuclear magnetic resonance spectroscopy. The compounds were found to possess moderate activity against Giardia duodenalis when compared to a metronidazole positive control.