Biological membranes are complex, self-organized structures that define boundaries and compartmentalize space in living matter. Composed of various lipid and protein molecules, these responsive surfaces mediate transmembrane signaling and material transport within the cell and with its environment. It is well known that lipid membrane properties change as a function of composition and phase state and that protein-lipid interactions can induce changes in the membrane’s properties and biochemical response. Here, molecular level changes in lipid organization induced by multivalent toxin binding were investigated using grazing incidence X-ray diffraction. Structural changes to lipid monolayers at the air-water interface and bilayers at the solid-water interface were studied before and after the specific binding of cholera toxin to membrane-embedded receptors. At biologically relevant surface pressures, protein binding perturbed lipid packing within monolayers and bilayers resulting in topological defects and the emergence of a new orientationally textured lipid phase. In bilayers this altered lipid order was transmitted from the receptor-laden exterior membrane leaflet to the inner leaflet, representing a potential mechanism for lipid-mediated outside-in signaling by multivalent protein binding. It is further hypothesized that cell surface micro-domains exhibiting this type of lipid order may serve as nucleation sites for vesicle formation in clathrin-independent endocytosis of cholera toxin.