  In this paper, we introduce a notion of a self-similar action of a group $G$
on a $k$-graph $\Lambda$, and associate it a universal C*-algebra
$\O_{G,\Lambda}$. We prove that $\O_{G,\Lambda}$ can be realized as the
Cuntz-Pimsner algebra of a product system. If $G$ is amenable and the action is
pseudo free, then $\O_{G,\Lambda}$ is shown to be isomorphic to a "path-like"
groupoid C*-algebra. This facilitates studying the properties of
$\O_{G,\Lambda}$. We show that $\O_{G,\Lambda}$ is always nuclear and satisfies
the Universal Coefficient Theorem; we characterize the simplicity of
$\O_{G,\Lambda}$ in terms of the underlying action; and we prove that, whenever
$\O_{G,\Lambda}$ is simple, there is a dichotomy: it is either stably finite or
purely infinite, depending on whether $\Lambda$ has nonzero graph traces or
not. Our main results generalize the recent work of Exel and Pardo on
self-similar graphs.
