We consider two models, the GI/M/s queue and the M/G/1 queue, in which waiting customers are served in random order. For each model we derive expressions for the calculation of the stationary waiting-time distribution function. Our methods differ from those of previous authors in that we do not use transforms, and consequently our results may be better suited for calculation. We illustrate our methods by deriving previously known results for the M/M/s and M/D/1 random-service queues, and by making sample calculations for the M/Ek/1 random-service queue for various values of the utilization factor and the index k.