In this paper we examine the properties of several cointegration tests when long run parameters are subject to multiple shifts, resorting to Monte Carlo methods. We assume that the changes in cointegration regimes are governed by a unobserved Markov chain process. This specification has the considerable advantage of allowing for an unspecified number of stochastic breaks, unlike previous works that consider a single, deterministic break. Our Monte Carlo analysis reveals that testing cointegration with the usual procedures is a quite unreliable task, since the performance of the tests is poor for a number of plausible regime shifts parameterizations.