Underwater acoustic local area networks (UA-LANs) can be used to improve the coverage of an underwater network by introducing a tier of local area communications. Media access control (MAC) is a crucial issue for UA-LANs. Existing MAC protocols for terrestrial WLANs cannot be directly applied to UA-LANs due to the acoustic channel features of limited bandwidth and high and variable propagation delay. In this paper, we propose a handshake based ordered scheduling MAC (HOSM) protocol for UA-LANs. The nodes with data packets to be transmitted first reserve the channel in a channel reservation phase. Then an order list is calculated, and the data packets of these nodes are transmitted according to this order list. We develop a control packets transmission adjustment mechanism to reduce collisions of control packets. The key idea of this mechanism is to utilize the information of propagation delay to adjust the time instant of control packets transmitting. To improve channel utilization, we present a variant Max-Min Ant System algorithm to calculate an optimal order for each data transmission round. Simulation results have confirmed that the proposed protocol can achieve high throughput with low delay and good spatial fairness.