We present the optical spectroscopy for the Blind Ultra Deep HI Environmental Survey (BUDHIES). With the Westerbork Synthesis Radio Telescope, BUDHIES has detected HI in over 150 galaxies in and around two Abell clusters at z=~0.2. With the aim of characterizing the environments of the Hi-detected galaxies, we obtained multifibre spectroscopy with the William Herschel Telescope. In this paper, we describe the spectroscopic observations, report redshifts and EW[OII] measurements for ~600 galaxies, and perform an environmental analysis. In particular, we present cluster velocity dispersion measurements for five clusters and groups in the BUDHIES volume, as well as a detailed substructure analysis.