I've turned free beta mobile application to paid version just by informing people about the change. Offered 40% discount to old users and it started to sell right away (license is around $20). There was people complaining about price but otherwise I got even positive feedback. However conversion rate was not that good but app had several hundreds of thousands users already so it turned out to be business after all (additionally to consumer markets we also sell enterprise versions).

I think it is important to have viable user base, you are going to lose a lot of your existing "customers". They signed up to free version so it is really unlikely that they start paying for it. Also if your free version hasn't attracted that much people, how it would attract if you ask money for it? Do change when you can lose 99% of your free users and still maintain valid business.

And what I almost forgot. You didn't mention what kind of segment you are targeting. Strategy heavily depends of that. If it is enterprise go premium like yesterday, if you are free they are not even interested. Consumers and small businesses are much more difficult.