The technologies using message queues, which correspond to asynchronous communication in distributed processing, have become remarkable. In particular, object-oriented persistent message queuing has obtained reliability in the asynchronous communication of middleware. On the other hand, XML is a promising database tool which enables interoperability of document exchange in the heterogeneous business environment. This paper presents an XML-based message queue which unifies the format of the message and realizes easy data exchange in different applications. First, we present the XML messaging architecture. We also propose relevant issues concerning XML messaging, including the structural representation and several XML messaging operations. Not only FIFO operations but also advanced operations can be designed using information contained within the messages, owing to XML's features. Second, we present message queuing by XML. The representation of the message queue by means of XML and concurrent access to the message queue are proposed. Finally, we report an implementation of the XML-based message queue using Java programming. Throughout this paper, we show the efficiency of the proposed XML-based message queue.