A Power System Stabilizer (PSS) is one of the most widely used power system controllers to enhance the stability of the power systems. In this paper, a new optimization technique for tuning PSSs in multi machine power system is presented. It is used to tune five PSSs in a 39-Bus IEEE New England network to enhance the small signal stability. The technique used is based on Low Discrepancy Sequence (LDS) or Quasi-Monte Carlo (QMC) algorithm. Different aspects regarding the application of this new algorithm are also presented. In addition, a comparison between LDS and one of the classical tuning methods namely Sequential Quadratic Optimization (SQP) is given. The results clearly demonstrate the effectiveness of the LDS method.