Monoterpenoid indole alkaloids (MIAs) represent a large class of plant natural products with marketed pharmaceutical activities against a wide range of indications, including cancer, malaria and hypertension. Halogenated MIAs have shown improved pharmaceutical properties; however, synthesis of new-to-nature halogenated MIAs remains a challenge. Here we demonstrate a platform for de novo biosynthesis of two MIAs, serpentine and alstonine, in baker’s yeast Saccharomyces cerevisiae and deploy it to systematically explore the biocatalytic potential of refactored MIA pathways for the production of halogenated MIAs. From this, we demonstrate conversion of individual haloindole derivatives to a total of 19 different new-to-nature haloserpentine and haloalstonine analogs. Furthermore, by process optimization and heterologous expression of a modified halogenase in the microbial MIA platform, we document de novo halogenation and biosynthesis of chloroalstonine. Together, this study highlights a microbial platform for enzymatic exploration and production of complex natural and new-to-nature MIAs with therapeutic potential.