Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code or mathematical formulas. Recent work has proposed grammar-constrained decoding (GCD), which restricts the LLM's output to follow a given grammar.As we demonstrate in this paper, however, existing GCD techniques can distort the LLM's distribution, leading to outputs that are grammatical but unlikely according to the LLM, and so ultimately low-quality. To address this issue, we propose grammar-aligned decoding (GAD), a new LLM decoding algorithm that both guarantees the output to be grammatical and better aligns with the LLM's distribution.Our algorithm is as a form of importance sampling, which gradually refines its estimates of the expected future grammaticality of different output prefixes during sampling. We evaluate GAD on both code generation and structured NLP tasks; our experiments demonstrate that GAD produces outputs with higher likelihood (according to the LLM's distribution) than existing GCD techniques, while still enforcing the desired grammatical constraints.