This paper proposes an efficient channel estimation scheme with a minimum number of pilots for a frequency-selective millimeter-wave communication system. We model the dynamics of the channel’s second-order statistics by a Markov process and develop a learning framework that finds the optimal precoding and combining vectors for pilot signals, given the channel dynamics. Using these vectors, the transmitter and receiver will sequentially estimate the corresponding angles of departure and arrival, and then refine the pilot precoding and combining vectors to minimize the error of estimating the small-scale fading of all subcarriers. Numerical results demonstrate near-optimality of our approach, compared to the oracle wherein the second-order statistics (not the dynamics) are perfectly known a priori.