We describe the design and implementation of a combinatorial exchange for trading catch shares in New South Wales, Australia. The exchange ended a decades-long political debate by providing a market-based response to a major policy problem faced by fisheries worldwide: the reallocation of catch shares in cap-and-trade programs designed to prevent overfishing. The exchange was conducted over the Internet to lower participation costs and allowed for all-or-nothing orders to avoid fragmented share portfolios. A subsidy was distributed endogenously to facilitate the transfer of shares from inactive to active fishers. Finally, prices were linear and anonymous to ensure that sellers of identical packages received the same payments. These features were crucial to mitigate economic distortions from introducing catch shares and to gain broad acceptance of the program. However, they led to computationally challenging allocation and pricing problems. The exchange operated from May to July 2017 and effectively reallocated shares from inactive fishers to those who needed them most: 86% of active fishers' bids were matched and their share deficits were reduced by 95% in high-priority share classes. Similar reallocation problems arise in fisheries with catch-share systems worldwide as well as in other cap-and-trade systems for resource rights, e.g., water and pollution rights. The implemented exchange illustrates how computational optimization and market design can provide policy tools, able to solve complex policy problems considered intractable only a few years ago.