Underwater sensor networks (UWSNs) have attracted a lot of attention recently. Since data in UWSNs are transmitted by acoustic signals, the characteristics of a UWSN are different from those of a terrestrial sensor network. In other words, the high propagation delay of acoustic signals in UWSNs causes spatial-temporal uncertainty, and makes transmission scheduling in UWSNs a challenging problem. Hence, in this paper, we propose a spatial-temporal MAC scheduling protocol, called ST-MAC, which is designed to overcome spatial-temporal uncertainty based on TDMA-based MAC scheduling for energy saving and throughput improvement. We construct thespatial-temporalconflictgraph(ST-CG) to describe the conflict delays among transmission links explicitly, and model ST-MAC as a new vertex coloring problem of ST-CG. We then propose a novel heuristic, called thetraffic-basedone-steptrialapproach(TOTA), to solve the coloring problem. In order to obtain the optimal solution of the scheduling problem, we also derive a mixed integer linear programming (MILP) model. Finally, we present a comprehensive performance study via simulations. The results show that ST-MAC can perform better than existing MAC schemes (such as S-MAC, ECDiG, and T-Lohi) in terms of the network throughput and energy cost.