Computing the complexity of Markov bases is an extremely challenging problem; no formula is known in general and there are very few classes of toric ideals for which the Markov complexity has been computed. A monomial curve $C$ in $\mathbb{A}^3$ has Markov complexity $m(C)$ two or three. Two if the monomial curve is complete intersection and three otherwise. Our main result shows that there is no $d\in \mathbb{N}$ such that $m(C)\leq d$ for all monomial curves $C$ in $\mathbb{A}^4$. The same result is true even if we restrict to complete intersections. We extend this result to all monomial curves in $\mathbb{A}^n, n\geq 4$.