A Markov modulated Poisson process (MMPP) is a Poisson process whose intensity varies according to a Markov process. We present a novel technique for simulating from the exact distribution of a continuous time Markov chain over an interval given the start and end states and the infinitesimal generator, and use this to create a Gibbs sampler which samples from the exact distribution of the hidden Markov chain in an MMPP. We apply the Gibbs sampler to modelling the occurrence of a rare DNA motif (the Chi site) and to inferring regions of the genome with evidence of high or low intensities for occurrences of this site.