We study the cosmological confinement-deconfinement phase transition (PT) of nearly conformal, strongly coupled large N field theories, applicable to composite Higgs models. We find that despite strong coupling, aspects of the PT can be analyzed when the confinement is predominantly spontaneous. In this scenario, the leading contribution to the transition rate can be computed within effective field theory of dilaton-- the pseudo Nambu-Goldstone boson associated with the spontaneous breaking of conformal symmetry. We then show how the holographic dual formulation in terms of 5D warped compactifications allows for qualitative understanding of the missing pieces of the earlier described 4D picture and a quantitative improvement of the calculations. In this description the PT is from a high-temperature black-brane phase to the low-temperature Randall-Sundrum I phase, and the transition proceeds by percolation of bubbles of IR-brane nucleating from the black-brane horizon. We show that the bubble configuration interpolating between the two phases can be smooth enough to be described within 5D effective field theory. We find that cosmological PT in the minimal models can complete only after a large period of supercooling, potentially resulting in excessive dilution of primordial matter abundances. We then show how generic modifications of the minimal models can result in a much faster completion of the PT. We also study the stochastic gravitational wave background produced by the violent bubble dynamics and discuss the implications of the PT for baryogenesis.