След 1973 г. се обмисля доставката на още магистрални дизелови локомотиви за допълване парка на БДЖ за линията Септември - Добринище и най-вече за замяната на парната тракция по линията Червен бряг - Оряхово. Доставката на локомотиви серия 75.000 се проваля по ред причини [1]. Така се сключва договор за строеж и доставка с румънския завод „23 август“ (сега „FAUR“) - Bucureşti. Локомотивите са строени по технически условия на БДЖ, в които са отразени опитът от вече 10-годишната експлоатация на локомотивите серия 75.000.
Първоначално е изработен прототип на локомотива, означен с номер 76-15 (предвиждало се след пробите машината да се върне в завода-производител за доработки, а локомотивите 76-01 до 76-14 са вече в процес на строителство), който да се достави като последен локомотив в серията. Програмата се осъществява и всички локомотиви са пуснати в експлоатация от май до септември 1977 г., а 76-15 пристига през февруари 1978 г.
Първоначално всички локомотиви серия 76.000 са зачислени в депо Червен бряг. Така се заменя изцяло парната тракция по линията. По-късно се установява, че броят им е по-голям от необходимия и 5 броя са изпратени в депо Септември (76-11 до 76-15). Експлоатацията им показва, въпреки близостта на техническите параметри до тези на серия 75.000, че са с по-ниски експлоатационни възможности, реализират повече откази, с по-ниско качество на изработка и др. След преустановяването експлоатацията на теснолинейката Червен бряг – Оряхово през 2002 г. се извършва бракуване на локомотиви в двете основни теснолинейни депа (Червен бряг и Септември) и в парка на БДЖ остават 4 локомотива серия 76.000. През 2009 година БДЖ продава 3 от тях в Аржентина, а един брой е оставен за музеен експонат и се съхранява в депо Септември.
