We study the persistence properties of a fractional Brownian motion whose Hurst exponent is a random variable instead of a fixed constant. For each fixed $H \in (0,1)$, it is well known that the persistence probability of an FBM below a constant barrier decays like $T^{-(1-H)+o(1)}$, as $T$ tends to infinity, cf. Molchan (1999). Our object of interest is the persistence probability of the process resulting from first randomly selecting $H\in (0,1)$ and then considering a fractional Brownian motion with this value of $H$ as a Hurst exponent, a process that is referred to as a fractional Brownian motion with random exponent. We prove that its persistence probability decays as $T^{-(1-H_0)+o(1)}$, as $T$ tends to infinity, where $H_0$ is the essential supremum of the distribution of the random Hurst exponent.