Battery energy storage system (BESS) has been recognized as a promising candidate for primary frequency control (PFC), thanks to its flexibility and fast response time. In this paper, we consider an aggregator that coordinates a number of BESSs to provide PFC service in the ancillary service market. To increase the profitability of the system, we propose an optimal online multi-BESS control algorithm that minimizes the penalty cost due to regulation failure. The algorithm is "online" in the sense that the control decisions are made without any knowledge of future information. Through rigorous analysis, we show that the proposed online algorithm achieves exactly the same performance as the optimal offline control, which assumes perfect knowledge of future information. Moreover, the computational complexity of the proposed algorithm is as low as solving a linear programming problem. Numerical results show that the proposed algorithm significantly outperforms a number of benchmark algorithms. Our work provides a useful theoretical foundation for optimal multi-BESS control that maximizes the economic benefits of BESSs in the ancillary service market.