Adequate damping is necessary to maintain the security and the reliability of power systems. The most-cost effective way to enhance the small-signal of a power system is to use power system controllers known as power system stabilizers (PSSs). In general, the parameters of these controllers are tuned using conventional control techniques such as root locus, phase compensation techniques, etc. However, with these methods, it is difficult to ensure adequate stability of the system over a wide range of operating conditions. Recently, there have been some attempts by researchers to use Evolutionary Algorithms (EAs) such as Genetic Algorithms (GAs), Particle Swarm Optimization, Differential Evolution (DE), etc., to optimally tune the parameters of the PSSs over a wide range of operating conditions. In this paper, a self-adaptive Differential Evolution (DE) is used to design a power system stabilizer for small-signal stability enhancement of a power system. By using self-adaptive DE, the control parameters of DE such as the mutation scale factor F and cross-over rate CR are made adaptive as the population evolves. Simulation results are presented to show the effectiveness of the proposed approach.