Let $L$ be a Lévy-type generator whose Lévy measure is controlled from below by that of a non-degenerate $α$-stable ($0<α<2$) process. In this paper, we study the martingale problem for the operator $\mathcal{L}_{t}=L+K_{t}$, with $K_{t}$ being a time-dependent non-local operator defined by \[ K_{t}f(x):=\int_{\mathbb{R}^{d}\backslash\{0\}}[f(x+y)-f(x)-\mathbf{1}_{α>1}\mathbf{1}_{\{|y|\le1\}}y\cdot\nabla f(x)]M(t,x,dy), \] where $M(t,x,\cdot)$ is a Lévy measure on $\mathbb{R}^{d}\backslash\{0\}$ for each $(t,x)\in \mathbb{R}_+ \times \mathbb{R}^{d}$. We show that if \[ \sup_{t\geq0,x\in\mathbb{R}^{d}}\int_{\mathbb{R}^{d}\backslash\{0\}}1\wedge|y|^βM(t,x,dy)<\infty \] for some $0<β<α$, then the martingale problem for $\mathcal{L}_{t}$ is well-posed.