The background lineated plains on Europa are locally highly modified and destroyed in regions known as chaos and lenticulae. Produced there are (1) isolated fragments and polygons of background material which rotate and translate, (2) matrix, which fills in the areas between the fragments and polygons, and (3) surface discolorations. Using observations and constraints from high-resolution Galileo images, we find that a model for the formation of these terrains which involves mobilization and migration of brines, and a possible percolation phase transition as the Europan lithosphere is warmed, can readily explain the vast majority of their characteristics. In addition, the presence of melt fractions of a few percent in the adjacent ice framework may enhance the creep rate and the accompanying deformation rates. The characteristics and distribution of lenticulae suggest that among the strong candidates for heat sources for brine migration and ice mobilization processes is diapirism linked to solid-state convection in a layer underlying a brittle lid and possibly overlying a liquid water layer. ¿ 1999 American Geophysical Union