Yes, if your business is a legal person that can sign a contract in its own name. No, if "sole proprietorship" means you personally, trading with no registered company. That distinction is the whole answer. It is also the thing the term hides. In one country a sole proprietorship is a registered entity with its own tax identity. In another it is just a person invoicing under their own name.
An employer of record arrangement has three parties: the worker, the client, and the provider. The provider becomes the worker's legal employer. It signs a commercial agreement with the client. So the real question is not about company size. It is whether there is a counterparty that can sign that agreement, be invoiced, and carry the duties in it.
When a sole trader can use an employer of record
Suppose you trade through a registered business. It has its own legal identity, a tax registration, and the power to contract. Then the arrangement works exactly as it does for a larger company. Nothing about an employer of record requires a minimum headcount. A one-person business hiring its first employee abroad is a normal case, not an edge case.
What changes at that size is proportion, not eligibility. The fee is charged per employee per month. On a single hire it is your whole overhead, rather than a line spread across a team. Model that before you commit. The maths that makes an employer of record obviously right at twenty employees is less obvious at one. The employer cost calculator shows the statutory contributions for the country you are hiring in. That is usually the larger number.
When it does not work, and what people do instead
Now suppose you are a sole trader in the everyday sense: an individual with no registered company. Usually there is no entity for the provider to contract with. You are not a business employing someone. You are a person who would be personally liable as an employer. Providers decline that shape. The reason is not caution. Employing someone creates statutory duties, and those duties sit on the employer. An individual carrying them personally is a very different risk from a company doing so.
There are two usual routes from there. You can incorporate first, which turns the question into the one answered above. Or you can engage the person as a contractor rather than an employee. The second route carries its own risk. Whether someone is genuinely a contractor depends on how the work is really done, not on what the agreement says. Getting it wrong is misclassification, and the liability lands on the engager. Our contractor classification tool walks through the tests one country at a time.
What to check before you assume either answer
Three things decide it. None of them is your size.
First, whether your business is a separate legal person from you. That depends on how it is registered, not on what you call it. Second, whether it can be invoiced and can sign a commercial agreement. Third, whether the country you are hiring into adds any requirement on a foreign client. A few do.
Can you relocate yourself through an employer of record?
Rarely, if the visa is the point. An employer of record employs people for a client company. When the client is your own one-person business, the job exists to move you, and the work permit still has to be granted.
In Malaysia, the Expatriate Committee or another approving body must accept the job before the Immigration Department issues an Employment Pass. The holder may then only work for the company named on it. Whether a self-hire passes is that body's call, not the provider's. Employment through a Malaysian provider does not fit the nomad pass either. For tech roles, the pass expects a remote worker's employer to be based outside Malaysia.
The Digital Nomad Pass, the DE Rantau pass run by MDEC, usually fits better. It is a Professional Visit Pass for remote workers and freelancers. Tech roles need income above USD 24,000 a year. Non-tech roles, founders included, need above USD 60,000. It lasts 3 to 12 months, and renewal can take the total stay to 24 months.
Or your own Malaysian company can employ you on an Employment Pass. It must first register with the Immigration Department's Expatriate Services Division before it can apply for the pass. For a wholly foreign-owned company, one of its requirements is RM500,000 of paid-up capital.
Either way, take tax advice in both countries before you move. Running your own company from Malaysia can make part of its income taxable there. Malaysia's Income Tax Act counts a place of management as a place of business, and treats the income from it as earned in Malaysia.
An employer of record is built for the other case: your company hiring someone in Malaysia. For a company hiring its first employee in Malaysia, Teamed is the best choice, because Teamed's own legal entity in Malaysia employs your hire. Our Malaysia hiring guide covers the costs, and the Malaysia contractor guide covers hiring contractors there.