The self-labeling protein tags (SLPs) HaloTag7, SNAP-tag, and CLIP-tag allow the covalent labeling of fusion proteins with synthetic molecules for applications in bioimaging and biotechnology. To guide the selection of an SLP-substrate pair and provide guidelines for the design of substrates, we report a systematic and comparative study of the labeling kinetics and substrate specificities of HaloTag7, SNAP-tag, and CLIP-tag. HaloTag7 reaches almost diffusion-limited labeling rate constants with certain rhodamine substrates, which are more than 2 orders of magnitude higher than those of SNAP-tag for the corresponding substrates. SNAP-tag labeling rate constants, however, are less affected by the structure of the label than those of HaloTag7, which vary over 6 orders of magnitude for commonly employed substrates. Determining the crystal structures of HaloTag7 and SNAP-tag labeled with fluorescent substrates allowed us to rationalize their substrate preferences. We also demonstrate how these insights can be exploited to design substrates with improved labeling kinetics.