The interconnected power system presents a great challenge to both system analyzers and control designers. The load-frequency control (LFC) problem has gained much importance because of the complexity and size of modern interconnected power systems. In this work, the original (full) system is decomposed into subsystems using the overlapping decentralization technique. A discrete-time output feedback control is then designed using Evolutionary Programming (EP) technique. EP is selected since it is a good candidate for a global search for the optimum of a cost function that leads to the optimum output feedback controller gains in order to achieve the LFC requirements and improve its performance. The system performance is analyzed through simulating different disturbances and parameter variations over a wide range. Results from Dynamic Programming technique are also presented for completeness.