Dehalogenases are environmentally important enzymes that detoxify organohalogens by cleaving their carbon-halogen bonds. Many microbial genomes harbour enzyme families containing dehalogenases, but a sequence-based identification of genuine dehalogenases with high confidence is challenging because of the low sequence conservation among these enzymes. Furthermore, these protein families harbour a rich diversity of other enzymes including esterases and phosphatases. Reliable sequence determinants are necessary to harness genome sequencing-efforts for accelerating the discovery of novel dehalogenases with improved or modified activities. In an attempt to extract dehalogenase sequence fingerprints, 103 uncharacterized potential dehalogenase candidates belonging to the α/β hydrolase (ABH) and haloacid dehalogenase-like hydrolase (HAD) superfamilies were screened for dehalogenase, esterase and phosphatase activity. In this first biochemical screen, 1 haloalkane dehalogenase, 1 fluoroacetate dehalogenase and 5 l-2-haloacid dehalogenases were found (success rate 7%), as well as 19 esterases and 31 phosphatases. Using this functional data, we refined the sequence-based dehalogenase selection criteria and applied them to a second functional screen, which identified novel dehalogenase activity in 13 out of only 24 proteins (54%), increasing the success rate eightfold. Four new L-2-haloacid dehalogenases from the HAD superfamily were found to hydrolyse fluoroacetate, an activity never previously ascribed to enzymes in this superfamily.