Zoals de naam al suggereert, is de Nieuwe Oosterbegraafplaats in de Watergraafsmeer niet de eerste Oosterbegraafplaats. Deze eer viel namelijk te beurt aan het terrein waar nu het Tropenmuseum staat. In 1866 opende hier de Oosterbegraafplaats. Deze begraafplaats heeft maar een kleine 30 jaar bestaan, want door de snelle stadsuitbreiding en de neiging van veel Amsterdammers toch niet het eeuwige leven te hebben, was er te weinig ruimte. Begin 20e eeuw werd het terrein gekocht door het Koninklijk Instituut voor de Tropen dat daar samen met het Koloniaal Museum een nieuw gebouw wilde neerzetten.
Toen het terrein was aangekocht, bleek echter dat niet alle graven geruimd mochten worden. Tijdens de bouw is er dus rondom een aantal graven heen gebouwd en bleef er een gedeelte van de begraafplaats bestaan. Pas in 1955 zijn de resterende graven geruimd om plaats te maken voor wat nu het Amstellyceum is. Voordat de bouw hier echter van begon, werden er door kinderen uit de buurt nogal wat schedels ontvreemd, die nooit meer zijn teruggevonden.
Onderstaand het grootste graf van de Nieuwe Oosterbegraafplaats, de graftombe van generaal van Heutsz, die op Atjeh in het toenmalig Nederlands-Indië flink huisgehouden heeft.
Het graf werd betaald door een inzameling onder zijn fans. Ze bleken zoveel bij elkaar gebracht te hebben, dat behalve dit graf er ook nog geld over was voor een extra monument, dat tegenwoordig op de Apollolaan te vinden is. Door de jaren heen is daar vrij veel protest tegen ontstaan, omdat men anders ging aankijken tegen de koloniale rol van Nederland in Indonesië. Ook de zoon van Van Heutsz, die in 1943 lid was van de SS, was het niet met het monument eens. Niet omdat hij iets tegen Nederland als koloniale macht had, maar omdat hij het monument te lafjes vond.
De Nieuwe Oosterbegraafplaats vierde intussen in 1994 haar eeuwfeest met de feestelijke opening van nieuwe crematieovens. Belangstellenden kregen toen een exclusief kijkje vanuit een crematieoven. Altijd reden voor een puik feestje!
