Studying materials at terapascal (TPa) pressures will provide insights into the deep interiors of large planets and chemistry under extreme conditions(1,2). The equation of state of aluminium is of interest because it is used as a standard material in shock-wave experiments and because it is a typical sp-bonded metal(1,3). Here we use density-functional-theory methods and a random-searching approach to predict stable structures of aluminium at multiterapascal pressures, finding that the low-pressure close-packed structures transform to more open structures above 3.2 TPa (nearly ten times the pressure at the centre of the Earth), with an incommensurate host -guest structure being stable over a wide range of pressures and temperatures. We show that the high-pressure phases may be described by a two-component model consisting of positive ions and interstitial electron 'blobs', and propose that such structures are common in sp-bonded materials up to multiterapascal pressures.