Combined cooling, heating and power (CCHP) systems have been considered as a potential energy saving technology for buildings due to their high energy efficiency and low carbon emission. Thermal energy storage (TES) can improve the energy efficiency of CCHP systems, since they reduce the mismatch between the energy supply and demand. However, it also increases the complexity of operation optimization of CCHP systems. In this study, a multi-agent system (MAS)-based optimal control method is proposed to minimize the operation cost of CCHP systems combined with TES. Four types of agents, i.e., coordinator agents, building agents, energy management agents and optimization agents, are implemented in the MAS to cooperate with each other. The operation optimization problem is solved by the genetic algorithm. A simulated system is utilized to validate the performance of the proposed method. Results show that the operation cost reductions of 10.0% on a typical summer day and 7.7% on a typical spring day are achieved compared with a rule-based control method. A sensitivity analysis is further performed and results show that the optimal operation cost does not change obviously when the rated capacity of TES exceeds a threshold.