Starch, being renewable and biodegradable, is a viable resource for developing sustainable and environmentally friendly materials. The potential of starch/Ca2+ gels based on waxy corn starch (WCS), normal corn starch (NCS), and two high-amylose corn starches, G50 (55% amylose content) and G70 (68% amylose content) as flame-retardant adhesives has been explored. Being stored at 57% relative humidity (RH) for up to 30 days, the G50/Ca2+ and G70/Ca2+ gels were stable without water absorption or retrogradation. The starch gels with increasing amylose content displayed increased cohesion, as reflected by significantly higher tensile strength and fracture energy. All the four starch-based gels showed good adhesive properties on corrugated paper. For wooden boards, because of the slow diffusion of the gels, the adhesive abilities are weak initially but improve with storage extension. After storage, the adhesive abilities of the starch-based gels are essentially unchanged except for G70/Ca2+, which peels from a wood surface. Moreover, all the starch/Ca2+ gels exhibited excellent flame retardancy with limiting oxygen index (LOI) values all around 60. A facile method for the preparation of starch-based flame-retardant adhesives simply by gelating starch with a CaCl2 solution, which can be used in paper or wood products, has been demonstrated.