This paper proposes a strategy for sizing a battery energy storage system (BESS) that supports primary frequency regulation (PFR) service of solar photo-voltaic plants. The strategy is composed of an optimization model and a performance assessment algorithm. The optimization model includes not only investment costs, but also a novel penalty function depending on the state of charge (SoC). This function avoids the existence of a potential inappropriate SoC trajectory during BESS operation that could impede the supply of PFR service. The performance assessment algorithm, fed by the optimization model sizing results, allows the emulation of BESS operation and determines either the success or failure of a particular BESS design. The quality of a BESS design is measured through number of days in which BESS failed to satisfactorily provide PFR and its associated penalization cost. Battery lifetime, battery replacements, and SoC are also key performance indexes that finally permit making better decisions in the election of the best BESS size. The inclusion of multiple BESS operational restrictions under PFR is another important advantage of this strategy since it adds a realistic characterization of BESS to the analysis. The optimization model was coded using GAMS/CPLEX, and the performance assessment algorithm was implemented in MATLAB. Results were obtained using actual frequency data obtained from the Colombian power system; and the resulting BESS sizes show that the number of BESS penalties, caused by failure to provide PFR service, can be reduced to zero at minimum investment cost.