Using molecular dynamics (MD) simulation, we have investigated the mechanical properties and the microstructural evolution of nanocrystalline tantalum (NC-Ta, grain size from 3.25 nm to ~13.0 nm) under uniaxial tension. The results show the flow stress at a given offset strain decreases as the grain size is decreased within the grain size regime studied, implying an inverse Hall-Petch effect. A strain rate sensitivity of ~0.14, more than triple that of coarse-grain Ta, is derived from the simulation results. Twinning is regarded to be a secondary deformation mechanism based on the simulations. Similar to nanocrystalline iron, stress-induced phase transitions from body-centered cubic (BCC) to face-centered cubic (FCC) and hexagonal close-packed (HCP) structures take place locally during the deformation process, The maximum fraction of FCC atoms varies linearly with the tensile strength. We can thus conclude that a critical stress exists for the phase transition to occur. It is also observed that the higher the imposed strain rate, the further delayed is the phase transition. Such phase transitions are found to occur only at relatively low simulation temperatures, and are reversible with respect to stress.