Increasing water demand due to population growth, irrigation expansion, industrial development, and the need for ecosystem improvements under mounting investment costs for developing new water sources calls for the efficient, equitable and sustainable management of water resources. This is particularly essential in the Aral Sea Basin (ASB) where ineffective institutions are the primary reason of intersectoral and inter-state water sharing conflicts and lack of sufficient investments for improving water use efficiency. This study examined market-based water allocation as an alternative option to the traditional administrative allocation to deal with water scarcity issues in the ASB. Potential economic gains of tradable water use rights were analyzed based on a newly constructed integrated hydro-economic river basin management model. The analysis differentiates between inter-catchment and intra-catchment water trading. The former does not consider any restrictions on water trading whereas the latter is based on the assumption that water trading is more likely to happen between neighboring water users located within the same catchment area. The analyses show that compared to fixed water allocation, inter-catchment water trading can improve basin-wide benefits by US$ 373 and US$ 476 million depending on water availability. Similarly, additional gains of US$ 259 to US$ 339 million are estimated under intra-catchment water trading depending on relative water availability. Trading gains are higher under drier conditions. However, water trading carries a series of transaction costs. We find that transaction costs exceeding US$0.05 per m3 of water traded wipe out the economic potential for water trading. Enforcement of the rule of law, infrastructural improvements, participation of representatives of all water stakeholders in decision making processes, and friendly relationships among the riparian countries are suggested as means for reducing transaction costs of water trading contracts.