We derive a theory that describes homogeneous nucleation of grain boundary (GB) phases. Our analysis takes account of the energy resulting from the GB phase junction, the line defect separating two different GB structures, which is necessarily a dislocation as well as an elastic line force due to the jump in GB stresses. The theory provides analytic forms for the elastic interactions and the core energy of the GB phase junction that, along with the change in GB energy, determines the nucleation barrier. We apply the resulting nucleation model to simulations of GB phase transformations in tungsten. Our theory explains why under certain conditions GBs cannot spontaneously change their structure even to a lower energy state.