Measles virus, Nipah virus, and multiple other paramyxoviruses cause disease outbreaks in humans and animals worldwide. The paramyxovirus matrix (M) protein mediates virion assembly and budding from host cell membranes. M is thus a key target for antivirals, but few high-resolution structures of paramyxovirus M are available, and we lack the clear understanding of how viral M proteins interact with membrane lipids to mediate viral assembly and egress that is needed to guide antiviral design. Here, we reveal that M proteins associate with phosphatidylserine and phosphatidylinositol 4,5-bisphosphate [PI(4,5)P2] at the plasma membrane. Using x-ray crystallography, electron microscopy, and molecular dynamics, we demonstrate that PI(4,5)P2 binding induces conformational and electrostatic changes in the M protein surface that trigger membrane deformation, matrix layer polymerization, and virion assembly.