Novaja Gazeta grundades av avhoppare från den kommunistiska tidningen Komsomolskaja Pravda. Chefredaktör 1995–2022 var Dmitrij Muratov, som också är en av tidningens grundare och som 2021 tilldelades Nobels fredspris tillsammans med den filippinska journalisten Maria Ressa. Sedan 2022 är Sergej Sokolov chefredaktör.