In cloud radio access networks (C-RANs), the baseband units and radio units of base stations are separated, which requires high-capacity fronthaul links connecting both parts. In this paper, we consider the delay-aware fronthaul allocation problem for C-RANs. The stochastic optimization problem is formulated as an infinite horizon average cost Markov decision process. To deal with the curse of dimensionality, we derive a closed-form approximate priority function and the associated error bound using perturbation analysis. Based on the closed-form approximate priority function, we propose a low-complexity delay-aware fronthaul allocation algorithm solving the per-stage optimization problem. The proposed solution is further shown to be asymptotically optimal for sufficiently small cross link path gains. Finally, the proposed fronthaul allocation algorithm is compared with various baselines through simulations, and it is shown that significant performance gain can be achieved.