The bacterial Shiga toxin is composed of an enzymatically active A-subunit, and a receptor-binding homopentameric B-subunit (STxB) that mediates intracellular toxin trafficking. Upon STxB-mediated binding to the glycolipid globotriaosylceramide (Gb3) at the plasma membrane of target cells, Shiga toxin is internalized by clathrin-dependent and independent endocytosis. The formation of tubular membrane invaginations is an essential step in the clathrin-independent STxB uptake process. However, the mechanism by which STxB induces these invaginations has remained unclear. Using a combination of all-atom molecular dynamics and Monte Carlo simulations we show that the molecular architecture of STxB enables the following sequence of events: the Gb3 binding sites on STxB are arranged such that tight avidity-based binding results in a small increment of local curvature. Membrane-mediated clustering of several toxin molecules then creates a tubular membrane invagination that drives toxin entry into the cell. This mechanism requires: (1) a precise molecular architecture of the STxB binding sites; (2) a fluid bilayer in order for the tubular invagination to form. Although, STxB binding to the membrane requires specific interactions with Gb3 lipids, our study points to a generic molecular design principle for clathrin-independent endocytosis of nanoparticles.