The electroweak phase transition in grand unified theory inspired SO(5)×U(1)×SU(3) gauge-Higgs unification is shown to be weakly first order and occurs at T=TcEW∼163 GeV, which is very similar to the behavior in the standard model in perturbation theory. A new phase appears at higher temperatures. SU(2)L×U(1)Y (θH=0) and SU(2)R×U(1)Y′ (θH=π) phases become almost degenerate above T∼mKK where mKK is the Kaluza-Klein mass scale (typically around 13 TeV) and θH is the Aharonov-Bohm phase along the fifth dimension. The two phases become degenerate at T=TcLR∼mKK. As the temperature drops in the evolution of the early Universe the SU(2)R×U(1)Y′ phase becomes unstable. The tunneling rate from the SU(2)R×U(1)Y′ phase to the SU(2)L×U(1)Y phase becomes sizable and a first-order phase transition takes place at T=2.5–2.6 TeV. The amount of gravitational waves produced in this left-right phase transition is small, far below the reach of the sensitivity of LISA. A detailed analysis of the SU(2)R×U(1)Y′ phase is also given. It is shown that the W boson, Z boson and photon, with θH varying from 0 to π, are transformed to gauge bosons in the SU(2)R×U(1)Y′ phase. Gauge couplings and wave functions of quarks, leptons, and dark fermions in the SU(2)R×U(1)Y′ phase are determined.