This paper presents a SOAP request scheduling algorithm for differentiated quality of service. The scheduling algorithm can be deployed on a Web services server or any server that processes SOAP requests. Due to the resource-intensive security processing of SOAP messages, this research implements the scheduling algorithm on a QoS security server. The security server schedules the requests forwarded from the Web services server for the security processing and then sends the valid requests back to the Web services server for executing the Web services. The design of the scheduling algorithm is derived from the traditional deficit round-robin scheduling. However, the scheduling algorithm schedules requests according to the probed CPU resource consumption of requests. In the evaluation, the scheduling algorithm reveals the service differentiation on the throughput and response time and the little scheduling overhead. The resource utilizations are measured to prove the security processing is much more resource-intensive than the Web services execution.