The paper shows that for every positive integer $p > 2$, there exists a compact non-orientable surface of genus $p$ with at least $4p$ automorphisms if $p$ is odd, or at least $8\,(p-2)$ automorphisms if $p$ is even, with improvements for odd $p\not\equiv 3$ mod 12. Further, these bounds are shown to be sharp (in that no larger group of automorphisms exists with genus $p$) for infinitely many values of $p$ in each congruence class modulo 12, with the possible (but unlikely) exception of 3 mod 12.