The physical state of embryonic tissues emerges from non-equilibrium, collective interactions among constituent cells. Cellular jamming, rigidity transitions and characteristics of glassy dynamics have all been observed in multicellular systems, but it is unclear how cells control these emergent tissue states and transitions, including tissue fluidization. Combining computational and experimental methods, here we show that tissue fluidization in posterior zebrafish tissues is controlled by the stochastic dynamics of tensions at cell-cell contacts. We develop a computational framework that connects cell behavior to embryonic tissue dynamics, accounting for the presence of extracellular spaces, complex cell shapes and cortical tension dynamics. We predict that tissues are maximally rigid at the structural transition between confluent and non-confluent states, with actively-generated tension fluctuations controlling stress relaxation and tissue fluidization. By directly measuring strain and stress relaxation, as well as the dynamics of cell rearrangements, in elongating posterior zebrafish tissues, we show that tension fluctuations drive active cell rearrangements that fluidize the tissue. These results highlight a key role of non-equilibrium tension dynamics in developmental processes.