Self-assembly of molecular units into complex and functional superstructures is ubiquitous in biology. The number of superstructures realized by self-assembly of man-made nanoscale units is also growing. However, assemblies of colloidal inorganic nanocrystals(1-3) are still at an elementary level, not only because of the simplicity of the shape of the nanocrystal building blocks and their interactions, but also because of the poor control over these parameters in the fabrication of more elaborate nanocrystals. Here, we show how monodisperse colloidal octapod-shaped nanocrystals self-assemble, in a suitable solution environment, on two sequential levels. First, linear chains of interlocked octapods are formed, and subsequently the chains spontaneously self-assemble into three-dimensional superstructures. Remarkably, all the instructions for the hierarchical self-assembly are encoded in the octapod shape. The mechanical strength of these superstructures is improved by welding the constituent nanocrystals together.