You can be employed through a third party deployment company (ArbeitnehmerÜberlassungsGesetz) for up to eighteen months. Such companies (known in other countries as Employer of Record / GEO / PEO / Umbrella companies) have an AÜG license.
We offer this to our clients in Germany. After eighteen months your company could setup (in order of complexity) a representative office, branch or subsidiary. Or you could pursue one of the self employed models.