A method is proposed to fit parameters of Power System Stabilizer controllers in electromechanical multimachine power systems. The use of the Non-dominated Sorting Genetic Algorithm II heuristic method and Tabu search is considered to be initial search criteria. These methods give an approximation of the values that define the controllers. Then, the stochastic approach was used to evaluate the behavior of the parameters found when considering the system’s response to the presence of random and self-sustained in-time disturbances that affect the response of the system under steady state. The stochastic approach allows the evaluation of the system’s response through the calculation of the cost of energy loss under steady state. The method is applied to two systems: a three-machine nine-busbar system, and the Interconnected System of the Greater North (Sistema Interconectado del Norte Grande) in Chile. For these systems, the proposed methodology effectively optimized the controllers and Tabu search was shown to have a better performance than the Non-dominated Sorting Genetic Algorithm II.