Flavin-dependent halogenases catalyse halogenation of aromatic compounds. In most cases, this reaction proceeds with high regioselectivity and requires only the presence of FADH2, oxygen, and halide salts. Since marine habitats contain high concentrations of halides, organisms populating the oceans might be valuable sources of yet undiscovered halogenases. A new Hidden-Markov-Model (HMM) based on the PFAM tryptophan halogenase model was used for the analysis of marine metagenomes. Eleven metagenomes were screened leading to the identification of 254 complete or partial putative flavin-dependent halogenase genes. One predicted halogenase gene (brvH) was selected, codon optimised for E. coli, and overexpressed. Substrate screening revealed that this enzyme represents an active flavin-dependent halogenase able to convert indole to 3-bromoindole. Remarkably, bromination prevails also in a large excess of chloride. The BrvH crystal structure is very similar to that of tryptophan halogenases but reveals a substrate binding site that is open to the solvent instead of being covered by a loop.