We consider a scenario where a power constrained transmitter delivers randomly arriving packets to the destination over Markov time-varying channel and adapts different transmission power to each channel state in order to guarantee successful transmission. To minimize the expected average transmission delay of each packet, we formulate the problem into a constrained Markov decision process (CMDP). We reveal the queue-length threshold structure of the optimal policy, i.e., the transmitter sends packets if and only if the queue length surpasses a threshold and obtain the optimal cross-layer scheduling strategy through linear programming (LP). Numerical results validate the performance of the proposed strategy and illustrate a delay-power tradeoff in such scenario.