This paper proposes a new approach for the simultaneous stabilization of multi-machine power system networks by tuning the parameters of power system stabilizers (PSS) using backtracking search algorithm (BSA). To enhance system damping, damping ratio based objective function is considered and widely used conventional lead-lag type PSS structure is used. The ability to lead the optimal design of the PSS regardless of the initial guess proves the robustness of the algorithm. The performances of the approach are investigated for two different multi-machine networks subjected to three phase fault and the results obtained from simulation verify the effectiveness of the proposed technique. The simulation results are also compared with a well-established swarm intelligence paradigm in this field called particle swarm optimization (PSO), which also gives confidence on the proposed technique.