Influenza virus infects cells by binding to sialylated glycans on the cell surface. While the chemical structure of these glycans determines hemagglutinin-glycan binding affinity, bimolecular affinities are weak, so binding is avidity-dominated and driven by multivalent interactions. Here, we show that membrane spatial organization can control viral binding. Using single-virus fluorescence microscopy, we demonstrate that the sterol composition of the target membrane enhances viral binding avidity in a dose-dependent manner. Binding shows a cooperative dependence on concentration of receptors for influenza virus, as would be expected for a multivalent interaction. Surprisingly, the ability of sterols to promote viral binding is independent of their ability to support liquid-liquid phase separation in model systems. We develop a molecular explanation for this observation via molecular dynamics simulations, where we find that cholesterol promotes small-scale clusters of glycosphingolipid receptors. We propose a model whereby cholesterol orders the monomeric state of glycosphingolipid receptors, reducing the entropic penalty of receptor association and thus favoring multimeric complexes without phase separation. This model explains how cholesterol and other sterols control the spatial organization of membrane receptors for influenza and increase viral binding avidity. A natural consequence of this finding is that local cholesterol concentration in the plasma membrane of cells may alter the binding avidity of influenza virions. Furthermore, our results demonstrate a form of cholesterol-dependent membrane organization that does not involve lipid rafts, suggesting that cholesterol's effect on cell membrane heterogeneity is likely the interplay of several different factors.