We reported previously the discovery of the potent antimalarial 40-membered macrolide bastimolide A (1) from the tropical marine cyanobacterium Okeania hirsute. Continued investigation has led to the discovery of a new analogue, bastimolide B (2), a 24-membered polyhydroxy macrolide with a long aliphatic chain and unique terminal tert-butyl group. Its complete structure was determined by a combination of extensive spectroscopic methods and comparative analysis of its methanolysis products with those of bastimolide A. A methanolysis mechanism for bastimolide A is proposed, and one unexpected isomerization product of the C2-C3 double bond, 2-(E)-bastimolide A (3), was obtained. Bastimolide B (2) showed strong antimalarial activity against chloroquine-sensitive Plasmodium falciparum strain HB3. A preliminary investigation of the structure-activity relationship based on six analogues revealed the importance of the double bond as well as the 1,3-diol and 1,3,5-triol functionalities.