Tom20 is located at the outer membrane of mitochondria and functions as a receptor for the N-terminal presequence of mitochondrial-precursor proteins. Recently, three atomic structures of the Tom20-presequence complex were determined using X-ray crystallography and classified into A-, M-, and Y-poses in terms of their presequence-binding modes. Combined with biochemical and NMR data, a dynamic-equilibrium model between the three poses has been proposed. To investigate this mechanism in further detail, we performed all-atom molecular dynamics (MD) simulations and replica-exchange MD (REMD) simulations of the Tom20-presequence complex in explicit water. In the REMD simulations, one major distribution and another minor one were observed in the converged free energy landscape at 300 K. In the major distribution, structures similar to A- and M-poses exist, whereas those similar to Y-pose are located in the minor one, suggesting that A-pose in solution is more stable than Y-pose. A k-means clustering algorithm revealed a new pose not yet obtained by X-ray crystallography. This structure has double salt bridges between Arg14 in the presequence and Glu78 or Glu79 in Tom20 and can explain the binding affinity of the complex in previous pull down assay experiments. Structural clustering and analyses of contacts between Tom20 and the presequence suggest smooth conformational changes from Y- to A-poses through low activation barriers. M-pose lies between Y- and A-poses as a metastable state. The REMD simulations thus provide insights into the energetics of the multiple-binding forms and help to detail the progressive conformational states in the dynamic-equilibrium model based on the experimental data.