This paper presents a new online Power System Stabilizer (PSS) design based on fuzzy wavelet network (FWN) to damp the multi-machine power system low frequency oscillations. The FWN, inspired by the wavelet theory and fuzzy concepts, is used to simultaneous design of two PSSs, in which error between system desired output and output of control object is directly utilized to tune the network parameters. The orthogonal least square (OLS) algorithm is used to determine network dimension, purify the wavelets for selecting efficient wavelets, and determine the number of sub- wavelet neural networks and fuzzy rules. In this paper, Shuffled Frog Leaping Algorithm (SFLA) is employed for learning of FWN parameters and to find the optimal values of the controller parameters. To illustrate the capability of the proposed approach, some numerical results are presented on a 2-area 4-machine system. To show the effectiveness and robustness of the designed supplementary controllers, a line-to-ground fault and also a three phase fault are applied at a bus. Furthermore, to make a comparison, two conventional PSSs are designed in which a lead-lag structure is considered for each PSS and its parameters are tuned using SFLA. The simulation results show the superiority and capability of the FWN based PSSs.