When did you introduce a premium/gold/non-free plan?

I'm currently contemplating whether or not I should introduce a premium plan for Megaproductive. At what point did you introduce a premium/gold/non-free plan for your product?

I'm working on some awesome new features, and although I don't want to hold anything back for my users, these features should provide them with enough value to justify a premium plan.