Major potentials of the millimeter (mmWave) bands have made it one of the most important components for the future mobile cellular and emerging WiFi networks with Gbps data rates. However, link establishment using “pencil-beams” introduces significant overhead. In this paper, we propose an adaptive and dynamic sector sweep and beam refinement protocols to reduce the signaling overhead associated with directional communications in mmWave bands. Our proposed solution takes the history of received signals into account and adjusts the beam alignment and refinement intervals. We implement the proposed solution on top of the IEEE 802.11ad standard. System-level simulations under mobile scenarios demonstrate the efficacy of the proposed techniques to reduce the overhead and latency.