  The electroweak phase transition in GUT inspired $SO(5)\times U(1) \times
SU(3)$ gauge-Higgs unification is shown to be weakly first order and occurs at
$T = T_c^{\rm EW} \sim 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 \times U(1)_Y$ ($\theta_H=0$) and $SU(2)_R \times
U(1)_{Y'}$ ($\theta_H=\pi$) phases become almost degenerate above $T \sim
m_{\rm KK}$ where $m_{\rm KK}$ is the Kaluza-Klein mass scale typically around
13$\,$TeV and $\theta_H$ is the Aharonov-Bohm phase along the fifth dimension.
The two phases become degenerate at $T = T_c^{\rm LR} \sim m_{\rm KK}$. As the
temperature drops in the evolution of the early Universe the $SU(2)_R \times
U(1)_{Y'}$ phase becomes unstable. The tunneling rate from the $SU(2)_R \times
U(1)_{Y'}$ phase to the $SU(2)_L \times U(1)_Y$ phase becomes sizable and a
first-order phase transition takes place at $T=2.5 \sim 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 Laser Interferometer Space Antenna
(LISA). A detailed analysis of the $SU(2)_R \times U(1)_{Y'}$ phase is also
given. It is shown that the $W$ boson, $Z$ boson and photon, with $\theta_H$
varying from 0 to $\pi$, are transformed to gauge bosons in the $SU(2)_R \times
U(1)_{Y'}$ phase. Gauge couplings and wave functions of quarks, leptons and
dark fermions in the $SU(2)_R \times U(1)_{Y'}$ phase are determined.
