Spin labeling was used to study the protein-protein interaction between the enzyme barnase (Bn) and its inhibitor barstar (Bs). A mutant of barstar (C40A), which contains only one cysteine, C82, located near the Bn-Bs contact region, was selectively modified by two spin labels having different lengths and structures of the flexible tether. The formation of a strong protein complex resulted in significant restriction of spin label mobility at the C82 residue of barstar, as indicated by notable changes in the recorded EPR spectra. The dependence of the separation between broad outer peaks of the EPR spectra on viscosity at constant temperature was used to evaluate the order parameter S and the rotational correlation time τ (a temperature-viscosity dependence approach). The order parameter S, which characterizes fast reorientation of a spin label relative to the protein molecule, sharply increases and approaches unity when Bs binds to Bn. In addition, formation of a Bs-Bs complex was observed; it is also accompanied by restriction of spin label mobility. At the same time, the rotational correlation times τ of spin-labeled Bs, its complex with Bn, and the Bs dimer in solution agree well with their molecular masses. This indicates that barstar, its complex with barnase, and barstar dimer are rigid protein entities. The described approach is suitable for studying any spin-labeled macromolecular complexes.