One important issue in power systems is dynamic instability due to loosing balance relation between electrical generation and a varying load demand that justifies the necessity of stabilization. Moreover, Power System Stabilizer (PSS) must have capability of producing appropriate stabilizing signals over a wide range of operating conditions and disturbances. To overcome these drawbacks, this paper proposes a new method for robust design of PSS by using an auto-tuning fuzzy control in combination with Real-Coded Genetic Algorithm (RCGA). This method includes two fuzzy controllers; internal fuzzy controller and supervisor fuzzy controller. The supervisor controller tunes the internal one by on-line applying of nonlinear scaling factors to inputs and outputs. The RCGA-based method is used for off-line training of this supervisor controller. The proposed PSS is tested in three operational conditions; nominal load, heavy load, and in the case of fault occurrence in transmission line. The simulation results are provided to compare the proposed PSS with conventional fuzzy PSS and conventional PSS. By evaluating the simulation results, it is shown that the performance and robustness of proposed PSS in different operating conditions is more acceptable