I think you may be misremembering. I'm pretty sure, at least in America, Netflix never charged extra for for Starz — it was either included in Netflix's catalog or not offered at all.

Maybe you're confusing Netflix with Amazon, who do offer Starz as an additional subscription? Or maybe you're just conflating the Starz catalog with Netflix's streaming service, which was originally part of the DVD service and then became its own thing?