Malaria is one of the most important infectious diseases worldwide. The causative of the most severe forms of malaria, Plasmodium falciparum, has developed resistances against all the available antimalarial drugs. In the present study, the phytochemical investigation of the green seaweed Halimeda macroloba has afforded two new compounds 1–2, along with 4 known ones 3–6. The structures of the compounds had been confirmed using 1& 2D-NMR and HRESIMS analyses. Extensive machine-learning-supported virtual-screening suggested cytochrome-C enzyme as a potential target for compound 2. Docking, absolute-binding-free-energy (ΔGbinding) and molecular-dynamics-simulation (MDS) of compound 2 revealed the strong binding interaction of this compound with cytochrome-C. In vitro testing for crude extract and isolated compounds revealed the potential in vitro inhibitory activity of both extract and compound 2 against P. falciparum. The crude extract was able to inhibit the parasite growth with an IC50 value of 1.8 ± 0.35 µg/mL. Compound 2 also showed good inhibitory activity with an IC50 value of 3.2 ± 0.23 µg/mL. Meanwhile, compound 6 showed moderate inhibitory activity with an IC50 value of 19.3 ± 0.51 µg/mL. Accordingly, the scaffold of compound 2 can be considered as a good lead compound for the future development of new antimalarial agents.