We present a new two-level rolling horizon optimization framework applied to a zero-emissions coal-fueled solid-oxide fuel cell power plant with compressed air energy storage for peaking applications. Simulations are performed where the scaled hourly demand for the year 2014 from the Ontario, Canada market is met as closely as possible. It was found that the proposed two-level strategy, by slowly adjusting the SOFC stack power upstream of the storage section, can improve load-following performance by 86% compared to the single-level optimization method proposed previously. A performance analysis indicates that the proposed approach uses the available storage volume to almost its maximum potential, with little improvement possible without changing the system itself. Further improvement to load-following is possible by increasing storage volumes, but with diminishing returns. Using an economically-focused objective function can improve annual revenue generation by as much as 6.5%, but not without a significant drop-off in load-following performance.