The characteristics of the two-step heated gel from walleye pollack surimi added with sodium gluconate (Na-gluconate) were investigated in connection with the progress of cross-linking reaction of myosin heavy chain (HC). The salt-ground meats with 2.5% NaCl plus either 8% sorbitol or Na-gluconate were preheated at 25°C or 40°C for various periods and were subsequently heated at 90°C for 30 min. There was no difference in the breaking strength of both two-step heated gels thus prepared, while the breaking strain of the gel formed with Na-gluconate was lower than that formed with sorbitol. Accordingly, the two-step heated gel with Na-gluconate was characterized as relatively more hard but not elastic. The same trends were also observed in the two-step heated gels prepared upon addition of Na-gluconate and NaCl by various ratios to adjust the Na+ concentration to 0.43 mol/kg. Although the addition of Na-gluconate decreased the progression rate of the cross-linking reaction of HC in the gels during heating, the changes in the characteristics of the two-step heated gels did not depend on the progress of such reaction. The results suggested that the changes in noncovalent interactions between proteins in the gels caused by gluconate ions largely contributed to the gel characteristics.