In the next-generation WiMAX system, cooperative communication is being considered as an advanced technique to increase the throughput and improve the signal quality. In a cooperative scenario, multiple stations can jointly emulate the antenna elements of a multi-input multi-output (MIMO) system in a distributed fashion. Unlike conventional space-time coding (STC) mechanisms used by a IEEE 802.16e antenna array, distributed space-time coding (DSTC) is employed across the cooperating stations to achieve a higher spatial diversity gain. In this paper, we present the framework for DSTC in the emerging relay-assisted WiMAX network, and develop a cooperative MAC layer protocol, called CoopMAX, for DSTC deployment in a WiMAX system. Through extensive simulations, we evaluate the performance of CoopMAX and show that DSTC can yield capacity gains of up to about 50% for the uplink of an IEEE 802.16 network.