Marine Cyanobacteria (blue-green algae) have been shown to possess an enormous potential to produce structurally diverse natural products that exhibit a broad spectrum of potent biological activities, including cytotoxic, antifungal, antiparasitic, antiviral, and antibacterial activities. Here, we report the isolation and structure determination of palstimolide A, a complex polyhydroxy macrolide with a 40-membered ring that was isolated from a tropical marine cyanobacterium collected at Palmyra Atoll. NMR-guided fractionation in combination with MS-based molecular networking and isolation via HPLC yielded 0.7 mg of the pure compound. The small quantity isolated along with the presence of significant signal degeneracy in both the H and C-NMR spectra complicated the structure elucidation of palstimolide A. Various NMR experiments and solvent systems were employed, including the LRHSQMBC experiment that allows the detection of long-range H-C correlation data across 4-, 5-, and even 6-bonds. This expanded NMR data set enabled the elucidation of the palstimolide's planar structure, which is characterized by several 1,5-disposed hydroxy groups as well as a -butyl group. The compound showed potent antimalarial activity with an IC of 223 nM as well as interesting anti-leishmanial activity with an IC of 4.67 µM.