The announcement of the new theory on when the Western Wall was built (see here and here) was not as dramatic as expected. The discovery of coins, the latest of which were struck by the Roman procurator Valeruis Gratus in 17-18 AD, in a mikveh that went out of use when the Western Wall was built over it, suggests that the building of the Temple Mount walls took decades. This is the full report released by the Israel Antiquities Authority.
This late date is not surprising, as at the beginning of Jesus’ ministry, usually dated to 30 AD, it was said that this Temple complex had been in building already for 46 years (John 2.20).
At the northern end of the Western Wall is a piece of bedrock that wasn’t even removed before the Temple was destroyed by the Romans in 70 AD.
This doesn’t mean to say that the Western wall is not Herodian. The whole building concept was designed by Herod the Great and completed after his death.