In this study, gelatin-gellan gum (GN-GG) composite gels were prepared by heat treatment, where the addition levels of GN and GG were optimized based on water-holding capacity (WHC) and swelling degree (SD). Furthermore, GN-GG composite gels added with Flammulina velutipes cellulose nanofibril (CNF) were prepared to improve the performance of GN-GG composite gels. Also, we investigated the effect of CNF on the WHC, SD, texture, rheology and microstructure of the composite gel. The results showed that the composite gel with 5% GN and 0.4% GG had good WHC and SD. The addition of CNF increased the WHC and SD and improved the storage and loss moduli, hardness, chewiness and gumminess of the composite gel. By measuring the ζ-potential and infrared spectrum of the composite gels, it was found that addition of CNF increased the absolute value of the ζ-potential, strengthened the hydrogen bond in the gel system, and increased the degree of protein crosslinking. The microstructure showed that CNF promoted the formation of gel networks and made the structure more uniform and compact. These findings show that the addition of CNF can improve the properties of composite gels and make the gel system more stable, and the suitable addition level of CNF is 0.6%.