Nano-sized archaeota, with their small genomes and limited metabolic capabilities, are known to associate with other microbes, thereby compensating for their own auxotrophies. These diminutive and yet ubiquitous organisms thrive in hypersaline habitats that they share with haloarchaea. Here, we reveal the genetic and physiological nature of a nanohaloarchaeon–haloarchaeon association, with both microbes obtained from a solar saltern and reproducibly cultivated together in vitro. The nanohaloarchaeon Candidatus Nanohalobium constans LC1Nh is an aerotolerant, sugar-fermenting anaerobe, lacking key anabolic machinery and respiratory complexes. The nanohaloarchaeon cells are found physically connected to the chitinolytic haloarchaeon Halomicrobium sp. LC1Hm. Our experiments revealed that this haloarchaeon can hydrolyze chitin outside the cell (to produce the monosaccharide N-acetylglucosamine), using this beta-glucan to obtain carbon and energy for growth. However, LC1Hm could not metabolize either glycogen or starch (both alpha-glucans) or other polysaccharides tested. Remarkably, the nanohaloarchaeon’s ability to hydrolyze glycogen and starch to glucose enabled growth of Halomicrobium sp. LC1Hm in the absence of a chitin. These findings indicated that the nanohaloarchaeon–haloarchaeon association is both mutualistic and symbiotic; in this case, each microbe relies on its partner’s ability to degrade different polysaccharides. This suggests, in turn, that other nano-sized archaeota may also be beneficial for their hosts. Given that availability of carbon substrates can vary both spatially and temporarily, the susceptibility of Halomicrobium to colonization by Ca. Nanohalobium can be interpreted as a strategy to maximize the long-term fitness of the host.