Although most accepted control algorithm is of proportional+integral+derivative (PID) structure in automatic voltage regulator (AVR) systems due to its effectiveness and simplicity, it is still a challenging task for researchers to tune its parameters efficiently. It is therefore of great interest, and constructs the motivation of this paper to undertake this task by incorporating the recently introduced, powerful optimization technique named as stochastic fractal search (SFS), for the first time in literature, which has the feature of increased accuracy and reduced convergence time. After optimizing the controller gains of K-p, K-i, and K-d, their performance is checked by using transient response analysis and then compared with those offered by recently published studies that use six competitive algorithms for achieving an efficient AVR system. To appraise the stability of the concerned power system tuned by SFS algorithm, root locus analysis and bode analysis are conducted along with the robustness analysis, which examines the system response to variations in the system parameters. Obtained comparative results affirm the excellence of SFS algorithm in achieving better PID parameters, and accordingly this yields an improved voltage response and minimized integral of time squared error in the output voltage profile.