Māori invented trench warfare in the 1800s. Their fortifications were surrounded by palisades, and they dug trenches beneath, shooting hapless British soldiers from the gaps between the ground and the bottom of the wall.
But I am not sure, if what you describe qualifies as trench warfare.
It's pretty incredible (and often terrible) what humans with hand tools can do when sufficiently organized and motivated.
The basic concept of a trench with something like a wooden barrier proximate goes back to neolithic times. Interestingly most of these sites we've found seem to not be fortifications but rather something ceremonial. It's ambiguous.
> The second siege was that of Padua in 1509. A monk engineer named Fra Giocondo, trusted with the defence of the Venetian city, cut down the city's medieval wall and surrounded the city with a broad ditch that could be swept by flanking fire from gun ports set low in projections extending into the ditch. Finding that their cannon fire made little impression on these low ramparts, the French and allied besiegers made several bloody and fruitless assaults and then withdrew.