In this Rapid Communication we study finite-temperature properties of spin-1/2 interacting bosons with spin-orbit coupling in two dimensions. When the ground state has stripe order, we show that thermal fluctuations will first melt the stripe order and lead to a superfluid of boson pairs if the spin-orbit coupling is isotropic or nearly isotropic. Such a phase supports fractionalized quantum vortices. The Kosterlitz-Thouless transition from superfluid to normal state is driven by proliferation of half vortices. When the ground state is a plane-wave state, the transition to normal state is driven by conventional Kosterlitz-Thouless transition. However, the critical temperature will drop to zero for isotropic spin-orbit coupling. © 2011 American Physical Society.