We study the stability of traveling waves of nonlinear Schr\"odinger equation with nonzero condition at infinity obtained via a constrained variational approach. Two important physical models are Gross-Pitaevskii (GP) equation and cubic-quintic equation. First, under a non-degeneracy condition we prove a sharp instability criterion for 3D traveling waves of (GP), which had been conjectured in the physical literature. This result is also extended for general nonlinearity and higher dimensions, including 4D (GP) and 3D cubic-quintic equations. Second, for cubic-quintic type sub-critical or critical nonlinearity, we construct slow traveling waves and prove their nonlinear instability in any dimension. For traveling waves without vortices (i.e. nonvanishing) of general nonlinearity in any dimension, we find the sharp condition for linear instability. Third, we prove that any 2D traveling wave of (GP) is transversally unstable and find the sharp interval of unstable transversal wave numbers. Near unstable traveling waves of above cases, we construct unstable and stable invariant manifolds.