Allocating space for storing heterogeneous messages in a message queue according to message classification. The classification may comprise message type, application type, network type, and so forth. Messages of multiple classification values may be queued in a single queue, referred to as a primary queue. When the allocated portion of the primary queue is reached for a particular message classification, then subsequent messages having that classification are sent to a secondary queue for queueing. The secondary queue also allocates space according to message classification. When space for a particular message classification becomes available in the primary queue, one or more messages having that classification may be moved from the secondary queue to the primary queue.