This paper deals with the robustness synthesis problem of three-parameter power system stabilizers (PSSs) having the common form which is widely used in industry. Computational characterization of the set of stabilizing PSSs is carried out using D-decomposition approach whereas the controller parameter space is subdivided into root invariant regions. The proposed technique is applied on a single machine infinite bus system (SMIB) which is commonly used in PSS design. Rather than Hurwitz stability, D-decomposition can improve the speed and quality of the response, and different convex regions in the complex plane are considered. A relatively stable region is chosen to guarantee better time domain specifications. Power system models such as the one studied suffers from uncertainties in the linear model parameters due to load patterns. An interval polynomial is developed to describe the model uncertainties using Kharitonov’s theorem. Enforcing time domain specifications like overshooting results in complex characteristic polynomials. The latter are tackled using the complex version of Kharitonov’s theorem. Robustness problem is converted into simultaneous stabilization of twelve Kharitonov’s plants. In order to avoid the conservatism of Kharitonov’s theorem for a parameter dependent system, and without suffering from computational burden, sufficient extreme plants are presented and stabilized. Simulation results confirm robust stability and performance of the proposed stabilizer over a wide range of operating conditions.