The standard M/G/1 queuing system is generalized so that the service time parameter becomes a stochastic process, {Mn, n = 1, 2, …}, indexed on the length of the queue at the moment service is begun. The service time, Ti, of a customer entering into service when a total of i customers are in the system is to be conditioned upon the random variable Mi. Some general theory is developed for the model and three specific cases are explored. For each of the examples, both the conditional service-time distributions, {BTn∣Mn(t∣μn), n = 1, 2, …}, and the prior distributions of {Mn}, {FMn(μn), n = 1, 2, …}, are specified, and results are obtained that characterize queue behavior using the imbedded Markov chain approach. The first case is an illustration of a random, non-state-dependent parameter, while the other two describe different ways a service parameter may be state-dependent. In addition, an industrial example based on the third case is cited.