I have been working for a company for about 3 years, mainly dealing with one client on daily basis. We had a great relationship, and I know the client insisted that he only wants to deal with me. However after my original employer encountered some financial difficulties I was let go. Since then I have formed my own company (6 months later) and I'm looking for clients. I know what my old client is not entirely happy with the service he is getting now and might be looking. Should I contact him and offer him my services? How should the message sound in order to not scare him off?
That depends on whether or not you are contractually obligated to honor a non-compete clause with your old employer.
If not, just approach the client like you would any other. If your company is to survive, you'll need to become really good at approaching potential clients so you may as well get some practice in.