The possibility of a strongly first-order electroweak phase transition is established in the minimal supersymmetric standard model with an extra $U(1)$, where a nontrivial CP violating phase is introduced in its Higgs sector. We find that there is a wide region in the parameter space of the model that allows the strongly first-order electroweak phase transition. The mass of stop quark need not be smaller than the top quark mass to ensure the first-order electroweak phase transition be strong. The effect of the CP violating phase upon the strength of the phase transition is discovered. The strength of the phase transition is reduced when the size of the CP violation is increased. For a given CP violating phase, we find that the model has a larger mass for the lightest Higgs boson when it has a stronger phase transition.