This paper proposes a new technique named BAT search algorithm to tune Power System Stabilizer (PSS) for the suppression of the low frequency oscillations in a multi-machine power system. The PSS parameter tuning problem is converted to an optimization problem with the time domain-based objective function and is solved by BAT search algorithm. The 3-generator and 9-bus power system has been used to validate the effectiveness of this tuning approach and the performance of the proposed BAT-based PSS (BATPSS) has been compared with Particle Swarm Optimization (PSO) based PSS (PSOPSS) under large disturbance. The nonlinear simulation results are represented to validate the effectiveness of the proposed BATPSS. In addition, the superiority of the proposed BATPSS over the PSOPSS is demonstrated.