In this paper, we present a new medium access control (MAC) protocol for ad-hoc networks with multiple input multiple output (MIMO) links. Links that use multiple element arrays (MEAs) at both ends are referred to as MIMO links. MIMO links are known to provide extremely high spectral efficiencies in multipath channels by simultaneously transmitting multiple independent data streams in the same channel. MAC protocols have been proposed in related work for ad-hoc networks with other classes of smart antennas such as switched beam antennas. However, as we substantiate in the paper, the unique characteristics of MIMO links necessitate an entirely new MAC protocol. We identify several advantages of MIMO links, and discuss key optimization considerations that can help in realizing an effective MAC protocol for such an environment. We present a centralized algorithm that has the optimization considerations incorporated in its design. Finally, we present a distributed protocol that approximates the centralized algorithm, and compare its performance against that of baseline protocols that are variants of the CSMA/CA protocol.