Consider the following nonlocal integro-differential operator: for $α\in(0,2)$, $$ \cal L^{(α)}_{σ,b} f(x):=\mbox{p.v.} \int_{\mathbb{R}^d-\{0\}}\frac{f(x+σ(x)z)-f(x)}{|z|^{d+α}}d z+b(x)\cdot\nabla f(x), $$ where $σ:\mathbb{R}^d\to\mathbb{R}^d\times\mathbb{R}^d$ and $b:\mathbb{R}^d\to\mathbb{R}^d$ are two $C^\infty_b$-functions, and p.v. stands for the Cauchy principal value. Let $B_1(x):=σ(x)$ and $B_{j+1}(x):=b(x)\cdot\nabla B_j(x)-\nabla b(x)\cdot B_j(x)$ for $j\in\mathbb{N}$. Under the following Hörmander's type condition: for any $x\in\mathbb{R}^d$ and some $n=n(x)\in\mathbb{N}$, $$ \mathrm{Rank}[B_1(x), B_2(x),\cdots, B_n(x)]=d, $$ by using the Malliavin calculus, we prove the existence of the heat kernel $ρ_t(x,y)$ to the operator $\cal L^{(α)}_{σ,b}$ as well as the continuity of $x\mapsto ρ_t(x,\cdot)$ in $L^1(\mathbb{R}^d)$ for each $t>0$. Moreover, when $σ(x)=σ$ is constant, under the following uniform Hörmander's type condition: for some $j_0\in\mathbb{N}$, $$ \inf_{x\in\mathbb{R}^d}\inf_{|u|=1}\sum_{j=1}^{j_0}|u B_j(x)|^2>0, $$ we also prove the smoothness of $(t,x,y)\mapstoρ_t(x,y)$ with $ρ_t(\cdot,\cdot)\in C^\infty_b(\mathbb{R}^d\times\mathbb{R}^d)$ for each $t>0$.