Exponential bounds probability [queue≥b]•ℝrsquo;e’-’γb are found for queues whose increments are described by Markov Additive Processes. This is done by application of maximal inequalities to exponential martingales for such processes. Through a thermodynamic approach the constant γ is shown to be the decay rate for an asymptotic lower bound for the queue length distribution. The class of arrival processes considered includes a wide variety of Markovian multiplexer models, and a general treatment of these is given, along with that of Markov modulated arrivals. Particular attention is paid to the calculation of the prefactor ℝrsquo;.