Trp-cage is a 20-residue miniprotein, which is believed to be the fastest folder known so far. In this study, the folding free energy landscape of Trp-cage has been explored in explicit solvent by using an OPLSAA force field with periodic boundary condition. A highly parallel replica exchange molecular dynamics method is used for the conformation space sampling, with the help of a recently developed efficient molecular dynamics algorithm P3ME/RESPA (particle-particle particle-mesh Ewald/reference system propagator algorithm). A two-step folding mechanism is proposed that involves an intermediate state where two correctly formed partial hydrophobic cores are separated by an essential salt-bridge between residues Asp-9 and Arg-16 near the center of the peptide. This metastable intermediate state provides an explanation for the superfast folding process. The free energy landscape is found to be rugged at low temperatures, and then becomes smooth and funnel-like above 340 K. The lowest free energy structure at 300 K is only 1.50 A Calpha-RMSD (Calpha-rms deviation) from the NMR structures. The simulated nuclear Overhauser effect pair distances are in excellent agreement with the raw NMR data. The temperature dependence of the Trp-cage population, however, is found to be significantly different from experiment, with a much higher melting transition temperature above 400 K (experimental 315 K), indicating that the current force fields, parameterized at room temperature, need to be improved to correctly predict the temperature dependence.