Artificial materials from the self-assembly of magnetic nanoparticles exhibit extraordinary collective properties; however, to date, the contribution of nanoscale magnetism to the mechanical properties of this class of materials is overlooked. Here, through a combination of Monte Carlo simulations and experimental magnetic measurements, this contribution is shown to be important in self-assembled superstructures of magnetite nanocubes. By simulating the relaxation of interacting macrospins in the superstructure systems, the relationship between nanoscale magnetism, nanoparticle arrangement, superstructure size, and mechanical stability is established. For all considered systems, a significant enhancement in cohesive energy per nanocube (up to 45%), and thus in mechanical stability, is uncovered from the consideration of magnetism. Magnetic measurements fully support the simulations and confirm the strongly interacting character of the nanocube assembly. The studies also reveal a novel super-size effect, whereby mechanically destabilization occurs through a decrease in cohesive energy per nanocube as the overall size (number of particles) of the system decreases. The discovery of this effect opens up new possibilities in size-controlled tuning of superstructure properties, thus contributing to the design of next-generation self-assembled materials with simultaneous enhancement of magnetic and mechanical properties.