With the emergence of cloud computing, on-demand resources usage is made possible. This allows applications to elastically scale out according to the load. One design pattern that suits this paradigm is the event-driven architecture (EDA) in which messages are sent asynchronously between distributed application instances using message queues. However, existing message queues are only able to scale for a certain number of clients and are not able to scale out elastically. We present the Elastic Queue Service (EQS), an elastic message queue architecture and a scaling algorithm which can be adapted to any message queue in order to make it scale elastically. EQS architecture is layered onto multiple distributed components and its management components can be integrated with the cloud infrastructure management. We have implemented a prototype of EQS and deployed it on a cloud infrastructure. A series of load testings have validated our elastic scaling algorithm and show that EQS is able to scale out in order to adapt to an applied load. We then discuss about the elastic scaling of the management layers of EQS and their possible integration with the cloud infrastructure management.