The earliest records we have of the Men-i-Naugrim date from the early centuries of the Second Age, when it served to connect Khazad-dûm, and other settlements in the Misty Mountains, with the Iron Hills beyond the Forest. At that point in history it was said to have been kept in good repair by the Dwarves, who at that time were widespread in Eriador. We know that Khazad-dûm, at least, was in existence during the First Age, and it's therefore entirely possible that the great Dwarf-road of the Greenwood dated back into those times.