You mean the Empire who surrendered to the Thalmor in the first place?
The Empire lost, it's a mystery they were even allowed to sign a peace agreement.
The same empire that lets the Thalmor run across Skyrim unopposed murdering those who keep a shrine to Talos?
This was happening before Stormcloak, he drew more attention to secret Talos worshipping with his ranting and raving. Now, thanks to Stormcloak, the Imperials can't look the other way when Nords are secretly worshipping. They've been put in the position of having to save the Nords from themselves, and not out of the kindness of their hearts, the whole Empire is on the line if they don't fix this.
The Nords were never actually allowed to practice in private but many did so in secret, whether or not Ulfric and his Stormcloaks forced the Empire to crack down is debateable but I am sure that the Empire would have done nothing if some Thalmor Inquisitors decided to abduct or murder anyone who they suspected of worshiping Talos.
It's made pretty clear in the dialogue from the very beginning that the Imperials had no interest in seriously enforcing that law, then Stormcloak had to open his big mouth and basically announce to the Aldmeri Dominion that the Empire wasn't keeping its end of the bargain (the peace they were sued for after losing a war).