In this paper, a novel bacterial foraging algorithm (BFA) based approach for robust and optimal design of PID controller connected to power system stabilizer (PSS) is proposed for damping low frequency power oscillations of a single machine infinite bus bar (SMIB) power system. This paper attempts to optimize three parameters (Kp, Ki, Kd) of PID-PSS based on foraging behaviour of Escherichia coli bacteria in human intestine. The problem of robustly selecting the parameters of the power system stabilizer is converted to an optimization problem which is solved by a bacterial foraging algorithm with a carefully selected objective function. The eigenvalue analysis and the simulation results obtained for internal and external disturbances for a wide range of operating conditions show the effectiveness and robustness of the proposed BFAPSS. Further, the time domain simulation results when compared with those obtained using conventional PSS and Genetic Algorithm (GA) based PSS show the superiority of the proposed design.