In this paper, we introduce a new class of generalized strongly set-valued nonlinear complementarity problems and construct new iterative algorithms. We show the existence of solutions for this kind of nonlinear complementarity problems and the convergence of iterative sequences generated by the algorithm. Our results extend some recent results in this field.