We classify all closed non-orientable P2-irreducible 3-manifolds having complexity up to 6 and we describe some having complexity 7. We show in particular that there is no such manifold with complexity less than 6, and that those having complexity 6 are precisely the 4 flat non-orientable ones. The manifolds having complexity 7 we describe are Seifert manifolds of type H2xS1, manifolds of type Sol, and manifolds with non-trivial JSJ decomposition.