Strongly interacting (QCD) matter is expected to exhibit a multifaceted phase structure: a hadron gas at low temperatures, a quark-gluon plasma at very high temperatures, nuclear matter in the low-temperature and high-density region, color superconductors at high densities. Most of the conjectured phases cannot yet be scrutinized by experiments but are based on model calculations. This monograph investigates the phases of QCD using a nonlocal covariant extension of the Nambu und Jona-Lasinio (NJL) model. This allows one to take into account the running of the QCD coupling strength at high and instanton physics at low energy scales. Gluon dynamics is implemented at finite temperatures and densities by coupling the nonlocal NJL model to a gluonic background field (expressed in terms of the Polyakov loop P). The thermodynamics of the resulting PNJL model describes both the chiral and the color-deconfinement transition. We obtain results in mean-field approximation, and extend them by including mesonic contributions to thermodynamic quantities. The phase-diagram region of finite density is investigated. A derivation of the nonlocal PNJL model from QCD first principles is also given.