Embryo morphogenesis is impacted by dynamic changes in tissue material properties, which have been proposed to occur via processes akin phase transitions (PTs). Here, we show that rigidity percolation provides a simple and robust theoretical framework to predict material/structural PTs of embryonic tissues from local cell connectivity. By using percolation theory, combined with directly monitoring dynamic changes in tissue rheology and cell contact mechanics, we demonstrate that the zebrafish blastoderm undergoes a genuine rigidity PT, brought about by a small reduction in adhesion-dependent cell connectivity below a critical value. We quantitatively predict and experimentally verify hallmarks of PTs, including power-law exponents and associated discontinuities of macroscopic observables at criticality. Finally, we show that this uniform PT depends on blastoderm cells undergoing meta-synchronous divisions causing random and, consequently, uniform changes in cell connectivity. Collectively, our theoretical and experimental findings reveal the structural basis of material PTs in an organismal context.