In the environment, vanadium-dependent haloperoxidases (VHPO) are likely to play a key role in the production of biogenic organo-halogens. These enzymes contain vanadate as a prosthetic group, and catalyze, in the presence of hydrogen peroxide, the oxidation of halide ions (Cl−, Br− or I−). They are classified according to the most electronegative halide that they can oxidize. Since the first discovery of a vanadium bromoperoxidase in the brown alga Ascophyllum nodosum thirty years ago, structural and mechanistic studies have been mainly conducted on two types of VHPO, chloro- and bromoperoxidases, and more recently on a vanadium-dependent iodoperoxidase. In this review, we highlight the main progress obtained on the structure-function relation of these proteins, based on biochemistry, crystallography and X-ray absorption spectroscopy (XAS). The comparison of 3D protein structures of the different VHPO helped identify the residues that govern the molecular mechanisms of catalysis and specificity of VHPO. Vanadium K-edge XAS gave further important insight to understand the fine changes around the vanadium cofactor during the catalytic cycle. The combination of different structural approaches, at different scales of resolution, shed new light on biological vanadium coordination in the active site, and its importance for the catalytic cycle and halide specificity of vanadium haloperoxidases.