Natural language-to-graph query generation (NL2GQL) requires schema-aware reasoning and multi-hop traversal planning, posing graph-specific challenges beyond the extensively studied Text-to-SQL setting. Existing NL2GQL systems typically solve each query in isolation, limiting their ability to learn from prior executions. We present ExGQL, an experience-guided framework for self-improving NL2GQL. ExGQL combines hierarchical memory, experience evolution, and capability synthesis to distill execution feedback into reusable reasoning strategies and convert validated strategies into executable capabilities. We further introduce a Failure-Directed Curriculum (FDC) for a separate practice phase, in which recurring failure patterns guide the selection of tasks that address the system’s current weaknesses. We evaluate ExGQL on NL2GQL-Bench, a benchmark of 400 expert-annotated graph query tasks over a production-scale graph database. ExGQL achieves an average accuracy of 0.869 versus 0.662 for the strongest evaluated baseline (+31% relative improvement), while reducing average query-generation time by 28%. In a separate practice phase, FDC reaches comparable accuracy of 0.861 with 60% fewer practice episodes and 36% lower runtime than fixed-order practice. These results show that NL2GQL systems can improve by reusing execution-derived experience, while failure-directed practice makes experience acquisition more efficient.