Queuing is commonly used to connect loosely coupled components to form large-scale, highly-distributed, and fault-tolerant applications. As cloud computing continues to gain popularity, a number of vendors have started offering cloud-hosted, multi-tenant queuing service. They provide high availability at the cost of reduced consistency. Although they offer at-least-once delivery guarantee, that is, no message loss, they do not make any effort in maintaining FIFO order, which is an important aspect of the queuing semantics. Thus they are not adequate for some applications. This paper presents the design and implementation of a scalable cloud-based queuing service, called Blue Dove Queuing Service (BDQS). It provides improved queuing consistency - at-least-once and best-effort in-order message delivery - while preserving high availability and reliability. It also offers clients a flexible trade-off between duplication and message order. Comprehensive evaluation is carried out on an Infrastructure-as-a-Service cloud computing platform with up to 70 server nodes and 1000 queues. It shows that BDQS achieves excellent performance scalability. Meanwhile, it offers an order-of-magnitude improvement in out-of-order measurement compared to existing no-order systems. Results also indicate that BDQS is highly reliable and available. © 2011 IEEE.