Akkermansia muciniphila, an abundant member of the human gut microbiota, has been suggested as a potential next-generation probiotic. However, its high sensitivity to oxygen limits the development of dosage protocols. Here, we describe microencapsulation, in a xanthan and gellan gum matrix, and a subsequent freeze-drying protocol for A. muciniphila DSM22959. For comparison Lactobacillus plantarum subsp. plantarum ATCC14917 was microencapsulated and freeze-dried using similar protocols. Four different mixtures were tested for cryoprotective properties: sucrose 5% plus trehalose 5%; agave syrup 10%; skim milk 10%, glucose 1%, yeast extract 0.5%, and mannitol 2.5%; as well as peptone 0.1% plus sorbitol 1.2%. Milli-Q-water served as control. Only cryoprotectant solutions with high sugar or protein content significantly improved the survival of both strains during freeze-drying. Microencapsulated cells were stored aerobically or anaerobically for 1 month at 4 °C or 25 °C. Survival of A. muciniphila was significantly better when stored anaerobically at 4 °C. The survival of microencapsulated L. plantarum, was relatively stable at both temperatures under anaerobic conditions. Survival of microencapsulated cells was compared with that of free cells during in vitro simulated upper gastrointestinal tract (GIT) transit at fasted and fed state. During in vitro simulated stomach passage, encapsulation significantly improved survival and viable cells remained at relevant levels after the entire simulated upper GIT transit. In conclusion, we here report a protocol for encapsulating A. muciniphila giving acceptable storage stability and enhancing survival during in vitro simulated upper GIT transit and thus constitutes an important step towards enabling future use of this important member of the human colonic microbiota as a probiotic.