We develop a Markovian master equation in the Lindblad form that enables the efficient study of a wide range of open quantum many-body systems that would be inaccessible with existing methods. The validity of the master equation is based entirely on properties of the bath and the system-bath coupling, without any requirements on the level structure within the system itself. The master equation is derived using a Markov approximation that is distinct from that used in earlier approaches. We provide a rigorous bound for the error induced by this Markov approximation; the error is controlled by a dimensionless combination of intrinsic correlation and relaxation timescales of the bath. Our master equation is accurate on the same level of approximation as the Bloch-Redfield equation. In contrast to the Bloch-Redfield approach, our approach ensures preservation of the positivity of the density matrix. As a result, our method is robust, and can be solved efficiently using stochastic evolution of pure states (rather than density matrices). We discuss how our method can be applied to static or driven quantum many-body systems, and illustrate its power through numerical simulation of a spin chain that would be challenging to treat by existing methods.