In this paper we show the Hörmander hypoelliptic theorem for nonlocal operators by a purely probabilistic method: the Malliavin calculus. Roughly speaking, under general Hörmander's Lie bracket conditions, we show the regularization effect of discontinuous Lévy noises for possibly degenerate stochastic differential equations with jumps. To treat the large jumps, we use the perturbation argument together with interpolation techniques and some short time asymptotic estimates of the semigroup. As an application, we show the existence of fundamental solutions for operator $\partial_t-\mathscr{K}$, where $\mathscr{K}$ is the nonlocal kinetic operator: $$ \mathscr{K} f(x,{\rm v}):={\rm p.v}\int_{\mathbb{R}^d}(f(x,{\rm v}+w)-f(x,{\rm v}))\frac{κ(x,{\rm v},w)}{|w|^{d+α}}{\rm d} w +{\rm v}\cdot\nabla_x f(x,{\rm v})+b(x,{\rm v})\cdot\nabla_{\rm v} f(x,{\rm v}). $$ Here $κ_0^{-1}\leq κ(x,{\rm v},w)\leqκ_0$ belongs to $C^\infty_b(\mathbb{R}^{3d})$ and is symmetric in $w$, p.v. stands for the Cauchy principal value, and $b\in C^\infty_b(\mathbb{R}^{2d};\mathbb{R}^d)$.