Algal-bacterial co-cultures, rather than cultures of algae alone, are regarded as having the potential to enhance productivity and stability in industrial algal cultivation. As with other inocula in biotechnology, to avoid loss of production strains, it is important to develop preservation methods for the long-term storage of these cultures, and one of the most commonly used approaches is cryopreservation. However, whilst there are many reports of cryopreserved xenic algal cultures, little work has been reported on the intentional preservation of both algae and beneficial bacteria in xenic cultures. Instead, studies have focused on the development of methods to conserve the algal strain(s) present, or to avoid overgrowth of bacteria in xenic isolates during the post-thaw recovery phase. Here, we have established a co-cryopreservation method for the long-term storage of both partners in a unialgal-bacterial co-culture. This is an artificial model mutualism between the alga Lobomonas rostrata and the bacterium Mesorhizobium loti, which provides vitamin B12 (cobalamin) to the alga in return for photosynthate. Using a Planer Kryo 360 controlled-rate cooler, post-thaw viability (PTV) values of 72% were obtained for the co-culture, compared to 91% for the axenic alga. The cultures were successfully revived after 6 months storage in liquid nitrogen, and continued to exhibit mutualism. Furthermore, the alga could be cryopreserved with non-symbiotic bacteria, without bacterial overgrowth occurring. It was also possible to use less controllable passive freezer chambers to cryopreserve the co-cultures, although the PTV was lower. Finally, we demonstrated that an optimised cryopreservation method may be used to prevent the overgrowth potential of non-symbiotic, adventitious bacteria in both axenic and co-cultures of L. rostrata after thawing.