The idea behind the folding core is simple: identify which residues of a protein are the first to form structure during folding and the last to lose structure during denaturation. However, defining this subset of residues is not trivial, and both simulation and experimental techniques have found it challenging. In this paper we present new techniques to elucidate the folding core; our approach uses methods for modeling and analyzing folding landscapes that are based on motion planning and rigidity analysis. We validate against known experimental data from folding core studies and show that folding core predictions from our new technique correlate well with experiment. We also compare our method to other computational methods and show that it performs better than the others in terms of sensitivity and better than all but one in terms of specificity. We also provide simulated relative hydrogen exchange rates which the other methods are unable to produce. In addition to correlating well with experiment, our method can suggest other components of rigid structure that have not been experimentally identified as part of the core because they were not previously measured. Our folding core analysis method and results obtained with it are publicly available on our server: http://parasol.tamu.edu/foldingserver/