Dating the building of Ephel Brandir is difficult. Its name strongly implies that it was built by Brandir, and that seems to be supported by the text of the The Silmarillion, where we're told that the Haladin dwelt there '...for Brandir son of Handir who ruled them ... trusted rather in secrecy than in deeds of war...' (Quenta Silmarillion 21, Of Túrin Turambar.).

This fits with what we know of the history of Brethil. In I 495, Brandir's father Handir saw the forest invaded by Orcs, set out to defend his lands and was killed in the fighting. There's no mention of any stronghold in the woods at this point, so it appears to have built by Brandir as a response to these events. If this is correct, then Brandir must have built the Ephel quickly: when Túrin arrived in Brethil the following year, the stronghold was already complete and functional.