The human malaria parasite Plasmodium falciparum genome is among the most A?+?T rich, with low complexity regions (LCRs) inserted in coding sequences including those for proteins targeted to its essential relict plastid (apicoplast). Replication of the apicoplast genome (plDNA), mediated by the atypical multifunctional DNA polymerase PfPrex, would require additional enzymatic functions for lagging strand processing. We identified an apicoplast-targeted, [4Fe-4S]-containing, FEN/Exo (PfExo) with a long LCR insertion and detected its interaction with PfPrex. Distinct from other known exonucleases across organisms, PfExo recognized a wide substrate range; it hydrolyzed 5'-flaps, processed dsDNA as a 5'-3' exonuclease, and was a bipolar nuclease on ssDNA and RNA-DNA hybrids. Comparison with the rodent P. berghei ortholog PbExo, which lacked the insertion and [4Fe-4S], revealed interspecies functional differences. The insertion-deleted PfExoΔins behaved like PbExo with a limited substrate repertoire because of compromised DNA binding. Introduction of the PfExo insertion into PbExo led to gain of activities that the latter initially lacked. Knockout of PbExo indicated essentiality of the enzyme for survival. Our results demonstrate the presence of a novel apicoplast exonuclease with a functional LCR that diversifies substrate recognition, and identify it as the candidate flap-endonuclease and RNaseH required for plDNA replication and maintenance.