A system and method can support different message queues in a transactional middleware machine environment. The transactional middleware machine environment includes an advertized table that comprises a first queue table and a second queue table, with the first queue table storing address information for a first message queue and the second queue table storing address information for a second message queue. The advertized table is further adaptive to be used by a first transactional client to locate a transactional service provided by a transactional server. The first transactional client operates to look up the first queue table for a key that indicates the address information of the transactional service that is stored in the second queue table.