We present a first attempt to determine nucleon-nucleon potentials in the parity-odd sector, which appear in 1P1, 3P0, 3P1, 3P2-3F2 channels, in Nf=2 lattice QCD simulations. These potentials are constructed from the Nambu-Bethe-Salpeter wave functions for J^P=0^-, 1^- and 2^-, which correspond to A1^-, T1^- and T2^- + E^- representation of the cubic group, respectively. We have found a large and attractive spin-orbit potential VLS(r) in the isospin-triplet channel, which is qualitatively consistent with the phenomenological determination from the experimental scattering phase shifts. The potentials obtained from lattice QCD are used to calculate the scattering phase shifts in 1P1, 3P0, 3P1 and 3P2-3F2 channels. The strong attractive spin-orbit force and a weak repulsive central force in spin-triplet P-wave channels lead to an attraction in the 3P2 channel, which is related to the P-wave neutron paring in neutron stars.