Various protein-labeling methods based on the specific interactions between genetically encoded tags and synthetic probes have been proposed to complement fluorescent protein-based labeling. In particular, labeling methods based on enzyme reactions have been intensively developed by taking advantage of the highly specific interactions between enzymes and their substrates. In this approach, the peptides or proteins are genetically attached to the target proteins as a tag, and the various labels are then incorporated into the tags by enzyme reactions with the substrates carrying those labels. On the other hand, we have been developing an enzyme-based protein-labeling system distinct from the existing ones. In our system, the substrate protein is attached to the target proteins as a tag, and the labels are incorporated into the tag by post-translational modification with an enzyme carrying those labels followed by tight complexation between the enzyme and the substrate protein. In this review, I summarize the enzyme-based protein-labeling systems with a focus on several typical methods and then describe our labeling system based on tight complexation between the enzyme and the substrate protein.