Deze begraafplaats, geopend in 1894, is in een aantal fases ontstaan. De oudste delen werden in 1889 en 1917 ontworpen door L.A. Springer. Daarna volgden nog uitbreidingen in 1930 (door Publieke Werken), 1942 en in 1959.
Er werd begonnen met 16 hectare. In totaal is de begraafplaats nu 33 ha groot.
Aanvankelijk wilde de gemeente op het terrein ook een crematorium en een mausoleum bouwen. Door geldgebrek werd daar van afgezien. Het crematorium kwam er in de jaren 1990 alsnog.
De begraafplaats heet Nieuwe Oosterbegraafplaats omdat ze de 'oude' Oosterbegraafplaats bij de Mauritskade verving. Die moest plaatsmaken voor het Oosterpark en later het Tropeninstituut.
De Nieuwe Ooster werd op 1 mei 1894 in gebruik genomen. Op die dag werd de oude begraafplaats gesloten. Tegelijk werd in het westelijke deel van de stad de oude Westerbegraafplaats gesloten en vervangen door een nieuwe, gelegen in de Amsterdammerpolder.
Diverse gebouwen van de Nieuwe Ooster werden ontworpen door stadsarchitect A.W. Weissman. Met het maken van die dienstgebouwen werd in 1892 begonnen. Er kwamen een ontvanggebouw (vervangen in 1939), een doodgraverswoning, een gebouw met drie knechtswoningen, een lijkenhuis en een barenhuis. Ook kwam er een monumentaal hek bij de hoofdingang.