Many decentralized markets are able to attain a stable outcome despite the absence of a central authority (Roth and Vande Vate, 1990). A stable matching, however, need not be efficient if preferences are weak. This raises the question whether a decentralized market with weak preferences can attain Pareto efficiency in the absence of a central matchmaker. I show that when agent tastes are independent, the random stable match in a large-enough market is asymptotically Pareto efficient even with weak preferences. In fact, even moderate-sized markets can attain good efficiency levels. The average fraction of agents who can Pareto improve is below 10% in a market of size n = 79 when one side of the market has weak preferences; when both sides have weak preferences, the inefficiency falls below 10% for n > 158. This implies that approximate Pareto efficiency is attainable in a decentralized market even in the absence of a central matchmaker.