In 2005, semi-hidden Markov models provided a rudimentary form of duration modelling. But they were computationally inefficient, as in the absence of knowing how long a state can last, all possibilities need to be accounted for. Our work proposed an innovative solution to this problem drawing upon the theoretical work in phase-type modelling. We incorporated the discrete Coxian distribution into the semi-Markov model and constructed efficient inference. This model was versatile and could approximate any duration distribution. It required minimal prior information - only the number of phases had to be specified. Our Coxian hidden semi-Markov model was as fast as the conventional Hidden Markov Models, and could additionally provide richer modelling of explicit duration distributions.