The premise of electric vehicles (EVs) participating in the frequency regulation (FR) of power systems is to satisfy the charging demands of users. In view of problems such as the uncertainty of EV users’ departure time and the increase in power supply pressure due to disordered charging in the frequency regulation process of EV clusters, a secondary frequency regulation control strategy with EVs considering user travel uncertainty is proposed. Firstly, EV charging history was analyzed, a reliability parameter was introduced to describe the user travel uncertainty, and an individual EV controllable domain model based on reliability correction was constructed. Then, EV clusters were grouped according to charging urgency and state of charge (SOC), and the controllable capacity of EV clusters was determined. Finally, EV frequency regulation capability parameters and charging urgency parameters were defined to determine the EV frequency regulation priority list, combined with the EV state grouping and priority list, and the EV cluster frequency control strategy was proposed. The simulation results show that the proposed strategy can satisfy the charging demands of users under uncertain travel conditions, reduce the power supply pressure of the power system caused by EVs entering the forced charging state, and effectively suppress frequency deviation.