Supramolecular host-guest interactions are an attractive driving force for the preparation of two- and three-dimensional materials. In this work, the fabrication of nano-sized capsules self-assembled by supramolecular interactions between specially designed complementary polymers using a sacrificial solid template is demonstrated. The alternate deposition of cyclodextrin and adamantane appended dextran polymers on gold nanoparticles followed by oxidative core dissolution yields well-ordered, stable and size-controlled nano-architectures, which are able to encapsulate small molecules with a good stability. This technology opens the way for using guest molecules with specific functions to build more sophisticated structures that react, for example, to light or electrochemical stimuli.