This paper presents a new algorithm for automatic tuning of decentralized PID control for two-input two-output (TITO) plants that fully extends the single-loop relay auto-tuner to the multiloop case. The tuning procedure consists of two stages. In the first, the desired critical point, which consists of the critical gains of the two loops and a critical frequency, is identified. Unlike SISO plants, there are infinitely many such points, and knowledge of the desired one is essential to the tuning procedure. The auto-tuner identifies the desired critical point with almost no a priori information on the process. During the identification phase, all controllers are replaced by relays, thus generating limit cycles with the same period in both loops. It is shown that each limit cycle corresponds to a single critical point of the process. By varying the relay parameters, different critical points can be determined, The auto-tuner contains a procedure that converges rapidly to the desired critical point while maintaining the amplitudes of the process variables as well as of the manipulated variables within prespecified ranges. In the second stage, the data of the desired critical point and possibly of other critical points is used to tune the PID controller by the Ziegler-Nichols rule or its modifications. This paper focuses on the first stage. The steady-state process gains, which are required for the appropriate choice of the desired critical point, are determined by the auto-tuner in closed-loop fashion simultaneously with the identification of the critical points. The identification of the process gains is achieved at no extra plant time. On the basis of a large number of simulated cases, the proposed auto-tuner seems to be efficient and robust. This paper discusses the underlying principles of the auto-tuner and its properties and capabilities demonstrated via examples. The algorithm is not limited to TITO cases, and can be extended to any number of loops.