Halogen substituents often lead to a profound effect on the biological activity of organic compounds. Flavin-dependent halogenases offer the possibility of regioselective halogenation at non-activated carbon atoms, while employing only halide salts and molecular oxygen. However, low enzyme activity, instability, and narrow substrate scope compromise the use of enzymatic halogenation as an economical and environmentally friendly process. To overcome these drawbacks, it is of tremendous interest to identify novel halogenases with high enzymatic activity and novel substrate scopes. Previously, Neubauer et al. developed a new hidden Markov model (pHMM) based on the PFAM tryptophan halogenase model, and identified 254 complete and partial putative flavin-dependent halogenase genes in eleven metagenomic data sets. In the present study, the pHMM was used to screen the bacterial associates of the Botryococcus braunii consortia (PRJEB21978), leading to the identification of several putative, flavin-dependent halogenase genes. Two of these new halogenase genes were found in one gene cluster of the Botryococcus braunii symbiont Sphingomonas sp. In vitro activity tests revealed that both heterologously expressed enzymes are active flavin-dependent halogenases able to halogenate indole and indole derivatives, as well as phenol derivatives, while preferring bromination over chlorination. Interestingly, SpH1 catalyses only monohalogenation, while SpH2 can catalyse both mono- and dihalogenation for some substrates.