In an extension of the Standard Model with a scalar color octet, the possibility of the strongly first-order electroweak phase transition is studied, by examining the finite-temperature effective Higgs potential at the one-loop level. It is found that there are wide regions in the parameter space that allow the strongly first-order electroweak phase transition, where the Higgs boson mass is larger than the experimental lower bound of 115 GeV, and the masses of the scalar color octet is around 200 GeV. The parameter regions may be explored at the LHC with respect to the electroweak phase transition.