Groups living on Cedar Mesa, SE Utah in the late Basketmaker II period (Grand Gulch phase, AD 200–400) were heavily maize-dependent, but lacked beans as a supplemental plant protein, and pottery vessels for cooking. Common occurrence of limestone fragments in their household middens suggests 1) limestone may have been used as the heating element for stone-boiling maize and 2) this practice might have made some maize proteins more available for human nutrition. Experiments examined these possibilities; results indicate that stone-boiling with Cedar Mesa limestone creates an alkaline cooking environment suitable for nixtamalization of maize kernels, and that maize cooked in this fashion shows significant increases in availability of lysine, tryptophan, and methionine. Archaeological limestone fragments from a Grand Gulch phase site show amounts of fragmentation and changes in density consistent with repeated heating. While not conclusive, these data indicate that further research (e.g., examination of archaeological limestone fragments for maize starch grains or phytoliths) is warranted. It is suggested that greater attention be paid to archaeological indications of stone-boiling with limestone among maize-dependent but pre-pottery societies.