The associations between biotin and the homologous proteins avidin and streptavidin are two of the most stable complexes found in nature, mainly because of very favorable van der Waals interactions between the ligand and the ideally preformed cavities of the receptors. Previous work, however, suggested that the large binding free energy in these two systems might be further enhanced by small modifications of the valeric acid side chain of biotin. We present in this study a new approach "computational fluorine scanning" as a means to assess how replacing hydrogen atoms with fluorine atoms in ligands could improve ligand binding free energies to their targets. This method allows us to rapidly evaluate and rank the association constants of these two proteins with biotin molecules that are fluoro-substituted on the valeric acid fragment. Our approach is based on a single molecular dynamics simulation of a reference ligand and the postprocessing of the trajectory, in which the reference is replaced by the mutated ligand, using the MM/PBSA free energy analysis. Our results, which are further supported by more elaborate free energy calculations and comparison with experiment, suggest that only one out of 9 investigated fluoro-substitutions, i.e., replacement of the pro-8R hydrogen atom of biotin with fluorine in the protein avidin, leads to a more favorable binding compared to the naturally occurring complex. Thus, we make a prediction that can be tested experimentally. This computational approach and variations thereof should be useful in the drug design process.