In this paper, we present a new medium access control (MAC) protocol for ad-hoc networks with multiple input multiple output (MIMO) links. MIMO links 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 coupled with several key optimization considerations, necessitate an entirely new MAC protocol. We identify several advantages of MIMO links, present a problem formulation for fair channel allocation when using such links, and discuss key optimization considerations that can help in realizing an effective MAC protocol for such an environment. We present a centralized algorithm called Stream-Controlled Medium Access (SCMA) that has the key optimization considerations incorporated in its design. Finally, we present a distributed SCMA protocol that approximates the centralized algorithm, and compare its performance against that of baseline protocols that are CSMA/CA variants.