We consider a phenomenological continuum theory for an active nematic fluid and show that there exists a universal, model-independent instability which renders the homogeneous nematic state unstable to order fluctuations. Using numerical and analytic tools we show that, in the vicinity of a critical point, this instability leads to a phase-separated state in which the ordered regions form bands in which the direction of nematic order is perpendicular to the direction of the density gradient. We argue that the underlying mechanism that leads to this phase separation is a universal feature of active fluids of different symmetries.