When the owners of my company decided to start their own company, I was the first employee they hired. I started working on the QMS before we even knew where our physical location would be. By the first day, we were four employees strong, and had document control, control of quality records, and other baseline procedures established. Naturally, some of these had to be altered once we actually started trying to implement some of them, but there was a start at least . . .
We received our certification within 6 months of opening the plant. I was able to train all of the employees (including the two owners) the "right way" to implement new products, new materials, accept customer orders, inspect raw materials/finished goods, and basically how to do business through our documented QMS from the very beginning. That way, they didn't develop bad habits that eventually had to be corrected.
I have to tell you, the opportunity to do this was the dream of a lifetime. To implement my own QMS from scratch without having to "undo" previous QMSs, or unlearn previous bad practices due to the lack of a QMS.