Cross-linked gelatin microgels were formed in gelatin-in-maltodextrin water-in-water (W/W) emulsions and evaluated as carriers of the enzyme β-galactosidase (β-Gal). The phase behavior of aqueous gelatin/maltodextrin mixtures was studied in detail, focusing on the multiphase region of the phase diagram that is constituted by three equilibrium phases: two immiscible aqueous phases plus one solid phase. The solid phase was analyzed by Raman spectroscopy, and water-in-water emulsions were formed within the multiphase region. Gelation of the dispersed gelatin droplets was induced by cooling and cross-linking with genipin, which is a natural cross-linking reagent of low toxicity, leading to the formation of gelatin microgel particles. These microgels were studied as delivery vehicles for the enzyme lactase, used as a model active component. Various incorporation methods of the enzyme were tested, to achieve highest encapsulation yield and activity recovery. Microgel particles, loaded with the enzyme, can be freeze-dried, and the enzyme remained active after a complete cycle of freeze-drying and rehydration. The stability of the enzyme at 37 °C under gastric and neutral pH conditions was tested and led to the conclusion that the cross-linked microgels could be suitable for use in food-industry, where β-Gal carriers are of interest for hydrolyzing lactose in milk products.