The coordinated movement of cell collectives is essential for normal epithelial tissue development, maintenance, and cancer progression. Here, we report on a minimal 3D extracellular matrix (ECM) system wherein both invasive collective migration (ICM) and rotational collective migration (RCM) arise spontaneously from individually seeded epithelial cells of mammary and hepatic origin, regardless of whether they express adherens junctions, and lead to ductal-like and acinar-like structures, respectively. Quantitative microscopy and cellular Potts modeling reveal that initial differences in cell protrusion dynamics and matrix-remodeling localization generate RCM and ICM behavior in confining 3D ECM. Matrix-remodeling activity by matrix metalloproteinases (MMPs) is localized to the base of protrusions in cells that initiate ICM, whereas RCM does not require MMPs and is associated with ITGβ1-mediated remodeling localized globally around the cell body. Further analysis in vitro and in vivo supports the concept that distinct matrix-remodeling strategies encode collective migration behaviors and tissue structure.