Using quantile regressions, we examine the relation between policy uncertainty, audit fees, and restatements in a sample of US firms from 2002 to 2018. We document that the association between policy uncertainty and audit fees is non-linear. For the clients in higher quantiles of audit fee distribution (high-fee-paying clients), we observe a reduction in audit fees during periods of uncertainty. Conversely, the clients in lower quantiles of audit fee distribution (low-fee-paying clients) experience an increase in audit fees. In addition, results show that the probability of restatements increases for the high-paying clients that get fee discounts in a high policy uncertainty period, while the probability of restatements decreases for the clients in the lower tail of fee distribution regardless of the fee pressure. This study offers valuable insights for policymakers and auditors, emphasizing the need to enhance audit regulations to ensure audit quality during uncertain times.