For two Polish state spaces $E_X$ and $E_Y$, and an operator $G_X$, we obtain existence and uniqueness of a $G_X$-martingale problem provided there is a bounded continuous duality function $H$ on $E_X \times E_Y$ together with a dual process $Y$ on $E_Y$ which is the unique solution of a $G_Y$-martingale problem. For the corresponding solutions $(X_t)_{t\ge 0}$ and $(Y_t)_{t\ge 0}$, duality with respect to a function $H$ in its simplest form means that the relation $\mathbb E_x[H(X_t,y)] = \mathbb E_y[H(x,Y_t)]$ holds for all $(x,y) \in E_X \times E_Y$ and $t\ge 0$. While duality is well-known to imply uniqueness of the $G_X$-martingale problem, we give here a set of conditions under which duality also implies existence without using approximating sequences of processes of a different kind (e.g.\ jump processes to approximate diffusions) which is a widespread strategy for proving existence of solutions of martingale problems. Given the process $(Y_t)_{t\ge 0}$ and a duality function $H$, to prove existence of $(X_t)_{t\ge 0}$ one has to show that the r.h.s.\ of the duality relation defines for each $y$ a measure on $E_X$, i.e.\ there are transition kernels $(μ_t)_{t\geq 0}$ from $E_X$ to $E_X$ such that $\mathbb E_y[H(x,Y_t)] = \int μ_t(x,dx')\, H(x',y)$ for all $(x,y) \in E_X \times E_Y$ and all $t\geq 0$. As examples, we treat resampling and branching models, such as the Fleming-Viot measure-valued diffusion and its spatial counterparts (with both, discrete and continuum space), as well as branching systems, such as Feller's branching diffusion. While our main result as well as all examples come with (locally) compact state spaces, we discuss the strategy to lift our results to genealogy-valued processes or historical processes, leading to non-compact (discrete and continuum) state spaces. Such applications will be tackled in forthcoming work based on the present article.