Assumably soon after the declaration of the Galactic Empire, the Clone trooper armors were replaced by the new Stormtrooper armors, in order to wipe away all memories and references to the former Grand Army of the Republic. But how soon were they introduced? How long would it take to re-equip an entire galactic army with new armors? When (BBY) did we see the very first Stormtrooper armors that we saw in A New Hope?
In the legends book Kenobi, Ben noticed that the clone trooper armour was different when he sees some on Tatooine a few months after he has gone into hiding.
We don't know if this was already the stormtrooper armour that we know, or if it was some interim model.
In the Disney Canon this timeframe is not so well covered. However; by the time of Star Wars Rebels, the standard Imperial armour is well-established.
According to the events of Star Wars Battlefront II, Anakin/Darth Vader's personal 501st Legion was equipped with Stormtrooper armour following Order 66:
In recognition of our loyalty and service to the Emperor, the 501st was placed under the direct command of Lord Vader. Armed with deadly new weapons, blazing new ships and shiny new armour, our presence lets the galaxy know that the days of the Old Republic are well and truly over. We were establishing a new era, an era of order and peace. - 501st Journal
The Dark Horse Comics mini-series Darth Vader and the Lost Command showed the 501st Legion in Phase II clone armour led by Darth Vader to conquer the Atoan system in late 19 BBY, the same year as the events of Revenge of the Sith.
According to Battlefront II, the 501st Legion was sent to assassinate Queen Apailana of Naboo in 18 BBY, and they were equipped in Stormtrooper armour.
As one of the Emperor's most favoured legions (considering he personally selected them after the First Battle of Geonosis to be his chosen legion to attack the Jedi Temple), they are likely to be among the first mainstream soldiers to receive the first pick of new military technology. As such, we can reasonably believe that the first batch of the finalised Stormtrooper armour was deployed into the Imperial Stormtrooper Corps by 18 BBY.