The Peccei-Quinn solution to the strong CP problem has a problematic aspect: it relies on a global U(1) symmetry which, although broken at low energy by the QCD anomaly, must be an extremely good symmetry of high-energy physics. This issue is known as the Peccei-Quinn quality problem. We propose a model where the Peccei-Quinn symmetry arises accidentally and is respected up to high-dimensional Planck-suppressed operators. The model is a SU(N) dark gauge theory with fermions in the fundamental and a scalar in the symmetric. The axion arises from the spontaneous symmetry breaking of the gauge group and the quality problem is successfully solved for large enough number of dark colors N. The model includes additional accidentally stable bound states which provide extra Dark Matter candidates beyond the axion.