A new three parameter natural extension of the Conway-Maxwell-Poisson (COM-Poisson) distribution is proposed. This distribution includes the recently proposed COM-Poisson type negative binomial (COM-NB) distribution [Chakraborty, S. and Ong, S. H. (2014): A COM-type Generalization of the Negative Binomial Distribution, Accepted in Communications in Statistics-Theory and Methods] and the generalized COM-Poisson (GCOMP) distribution [Imoto, T. :(2014) A generalized Conway-Maxwell-Poisson distribution which includes the negative binomial distribution, Applied Mathematics and Computation, 247, 824-834]. The proposed distribution is derived from a queuing system with state dependent arrival and service rates and also from an exponential combination of negative binomial and COM-Poisson distribution. Some distributional, reliability and stochastic ordering properties are investigated. Computational asymptotic approximations, different characterizations, parameter estimation and data fitting example also discussed.