The design of power system stabilizer (PSS) is load-dependent and needs continuous adjustment at each operating condition. This paper aims at introducing a robust non-fragile PSS for interconnected power systems. The proposed controller has the capability of adaptively tuning online its rule-base through a variable-structure direct adaptive control algorithm in order to rigorously attain the desired objectives. The PSS controller acts on damping the electromechanical modes of oscillations not only through a wide range of operating conditions but also in presence of different disturbances. Using MATLABTM-Simulink, simulation results significantly verify that the proposed controller provides favorable performance and efficiently contributes towards enhancing the system dynamic behavior when applied to the four machines two-area power system that mimics the typical system behavior in actual operation. The interaction between the variable-structure adaptive fuzzy-based power system stabilizer (VS-AFPSS) and the existed typical ones inside the interconnected power systems has been explicitly discussed. Compared to other conventional controllers, VS-AFPSS enables better damping characteristics to both local and inter-area oscillation modes considering different operating conditions and sever disturbances.