Provided are a method, computer program product and system for providing indexed queue support for efficient retrieval of messages from a queue. An index key for expediting message retrieval is assigned to a message when the operation of placing the message on a queue is committed. The index key assigned at commit time comprises an attribute (such as a message ID or correlation ID) specified by the sending application program, which placed the message on the queue. This deferred assignment of an index key until commit time means that the index key can be used to search for messages having the particular attribute without any possibility of identifying messages for retrieval before the messages have been committed. This maintains transactional requirements of a transaction-oriented messaging system which requires a message to only be made available for retrieval by receiver application programs after the sender application's put operation has committed.