Adhesion and insertion of curvature-mediating proteins can induce dramatic structural changes in cell membranes, allowing them to participate in several key cellular tasks. The way proteins interact to generate curvature remains largely unclear, especially at early stages of membrane remodeling. Using a coarse-grained model of Bin/amphiphysin/Rvs domain with an N-terminal helix (N-BAR) interacting with flat membranes and vesicles, we demonstrate that at low protein surface densities, binding of N-BAR domain proteins to the membrane is followed by a linear aggregation and the formation of meshes on the surface. In this process, the proteins assemble at the base of emerging membrane buds. Our work shows that beyond a more straightforward scaffolding mechanism at high bound densities, the interplay of anisotropic interactions and the local stress imposed by the N-BAR proteins results in deep invaginations and endocytic vesicular bud-like deformations, an order of magnitude larger than the size of the individual protein. Our results imply that by virtue of this mechanism, cell membranes may achieve rapid local increases in protein concentration.