  In this paper we construct supersymmetric Pati-Salam (PS) models containing
the minimal supersymmetric standard model and an invisible axion. The models
include two discrete symmetries, $\mathbb{Z}_4^R \times \mathbb{Z}_N$, which
maintain the $quality$ of the accidental Peccei-Quinn (PQ) symmetry and thus
the solution to the strong CP problem. We require that the discrete anomaly
conditions are satisfied for both $\mathbb{Z}_4^R \times G_{\rm PS}^2$ and $
\mathbb{Z}_N \times G_{\rm PS}^2$. The vacuum expectation value of the PQ field
spontaneously breaks all the discrete symmetries. R-parity is violated if any
of the PQ field(s) has an odd charge under $\mathbb{Z}_4^R$. We present two
explicit models which we refer to as a minimal model where R-parity violation
is extremely suppressed, and a non-minimal model where R-parity violation is
significant. In the latter model, the neutralino becomes unstable even if it is
the Lightest Supersymmetric Particle (LSP), and, in addition, there are new
low-energy vector-like states. In both examples, R-parity violation is
sufficiently suppressed such that the proton is stable.
