The coupling of power and heating systems can promote renewable energy integration and improve the comprehensive efficiency of the energy system. Advanced adiabatic compressed air energy storage (AA-CAES) is a large-scale clean energy storage technology with the potential for multi-energy co-storage and supply, which can serve as an energy hub integrating power and heating systems. However, the current bidding mechanism for AA-CAES participating in electricity and heating markets as an independent entity remains unclear, and traditional modeling mostly adopts battery-like energy storage models, leading to difficulties in accurately measuring economic benefits. To address this, this paper proposes a leader-follower game-based bidding strategy for AA-CAES considering combined heat and power supply. Firstly, a combined heat and power mathematical model of AA-CAES is established by accounting for the operational characteristics of each component. Secondly, a single-leader-dual-followers leader-follower game framework is constructed, where the upper layer optimizes bidding parameters with the goal of maximizing AA-CAES’s profit, and the lower layer achieves market clearing with the objective of maximizing social welfare. To solve the challenge of solving the bi-level nonlinear model, the Karush-Kuhn-Tucker (KKT) optimality conditions and binary expansion linearization method are adopted to convert it into a single-level mixed-integer programming problem. Finally, case simulations show that AA-CAES’s profit from participating in both markets increases by 30.6% compared with participating only in the electricity market. The parameters of its own components have a significant impact on profits—especially a 10% improvement in the isentropic efficiency of the turbine can increase total profits by 28%. This study provides key references for the market operation and parameter optimization of AA-CAES.