If you have an “Aufenthaltsgestattung”, i.e. a proof of arrival ("Ankunftsnachweis") or a "Duldung", your access to the labour market will remain limited. Self-employment is in principle not allowed and to work as an employee, you must first apply for a work permit at your immigration office ("Ausländerbehörde").
Asylum seekers can obtain a work permit if they have been in Germany for 3 months and are no longer obliged to live in an initial reception facility. If you still have to live in an initial reception centre, in case you have underage children, you can obtain a work permit after 6 months- and if you don't have children, after 9 months. Rejected asylum seekers whose application have been rejected due to Doublin Agreement, i.e. other EU countries are responsible for their case AND those who come from a safe country of origin and have applied for asylum after August 31, 2015, cannot obtain work permits. You can find out more about the safe countries of origin in our chapter "Safe countries of origin".
IMPORTANT: Your work permit will be only valid for a specific job. Your future boss will need to fill a form to describe the offered position, and you should apply for a work permit. Once both forms have been filled and submitted, the immigration office is obliged to react within two weeks. If you have not received any answer, contact a counselling centre or lawyer. You can also submit an emergency application to the Administrative Court. On Proasyl you can find counselling centres in your area.