BAR superfamily domains shape membranes through poorly understood mechanisms. We solved structures of F-BAR modules bound to flat and curved bilayers using electron (cryo)microscopy. We show that membrane tubules form when F-BARs polymerize into helical coats that are held together by lateral and tip-to-tip interactions. On gel-state membranes or after mutation of residues along the lateral interaction surface, F-BARs adsorb onto bilayers via surfaces other than their concave face. We conclude that membrane binding is separable from membrane bending, and that imposition of the module's concave surface forces fluid-phase bilayers to bend locally. Furthermore, exposure of the domain's lateral interaction surface through a change in orientation serves as the crucial trigger for assembly of the helical coat and propagation of bilayer bending. The geometric constraints and sequential assembly of the helical lattice explain how F-BAR and classical BAR domains segregate into distinct microdomains, and provide insight into the spatial regulation of membrane invagination.