Animal tissues exist within a continuum of fluid to solid states, and transitions between states are important for embryonic development, wound healing and cancer metastasis. Fluid-to-solid transitions are governed by the ratio of adhesive energy to kinetic energy. Here, we find that presomitic mesoderm solidification is driven by an intrinsic decline in cell speed along with an increase in adhesion mediated by Cadherin 2 in parallel with fibronectin and its receptor Integrin alpha 5. A computational model of cell-cell adhesion in the central tissue mesenchyme and cell-ECM adhesion on the tissue surface explains the observed phenotypes. Further, we identify negative feedback within the ECM as fibronectin supports the formation of a separate layer of Fibrillin 2b matrix that inhibits solidification. These data reveal a tissue fluidity code in which solidification is promoted by cadherins in parallel with Integrin alpha 5 and fibronectin, whereas negative feedback through Fibrillin 2b promotes fluidization.