In this paper, we study the codes over the matrix ring over $\mathbb{Z}_4$, which is perhaps the first time the ring structure $M_2(\mathbb{Z}_4)$ is considered as a code alphabet. This ring is isomorphic to $\mathbb{Z}_4[w]+U\mathbb{Z}_4[w]$, where $w$ is a root of the irreducible polynomial $x^2+x+1 \in \mathbb{Z}_2[x]$ and $U\equiv$ ${11}\choose{11}$. We first discuss the structure of the ring $M_2(\mathbb{Z}_4)$ and then focus on algebraic structure of cyclic codes and self-dual cyclic codes over $M_2(\mathbb{Z}_4)$. We obtain the generators of the cyclic codes and their dual codes. Few examples are given at the end of the paper.