In a deregulated power system uncertainty exists and lack of sufficient damping can lead to Low Frequency Oscillations (LFO). The problem can be addressed using robust Power System Stabilizers (PSS). In this paper, an optimal procedure to design a robust PID-PSS using interval arithmetic for the Single Machine Infinite Bus (SMIB) power system is proposed. The interval modelling captures the wide variations of operating conditions in bounds of system coefficients. In the proposed design procedure, simple and new closed loop stability conditions for an SMIB interval system are developed and are used to design an optimum PID-PSS for improving the performance of an SMIB system. The optimum PID-PSS is attained by tuning the parameters using the FMINCON tool provided in MATLAB. The robustness of the proposed PID-PSS design is validated and compared to other notable methods in the literature when the system is subjected to different uncertainties. The simulation results and performance error values show the effectiveness of the proposed robust PID-PSS controller.