Điều 8, 9 Luật người lao động Việt Nam đi làm việc ở nước ngoài theo hợp đồng năm 2006 quy định như sau:

"Điều 8. Doanh nghiệp hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài

1. Hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài là ngành, nghề kinh doanh có điều kiện.

2. Doanh nghiệp hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài (sau đây gọi là doanh nghiệp dịch vụ) phải có vốn pháp định theo quy định của Chính phủ và được cơ quan nhà nước có thẩm quyền cấp Giấy phép hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài.

3. Doanh nghiệp được cấp Giấy phép phải trực tiếp tổ chức hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài.

4. Chính phủ quy định các loại hình doanh nghiệp được hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài phù hợp với tình hình phát triển kinh tế - xã hội trong từng giai đoạn và lộ trình hội nhập kinh tế quốc tế.

Điều 9. Điều kiện cấp Giấy phép

Doanh nghiệp có vốn pháp định quy định tại khoản 2 Điều 8 của Luật này có đủ các điều kiện sau đây thì được cấp Giấy phép:

1. Có đề án hoạt động đưa người lao động đi làm việc ở nước ngoài;

2. Có bộ máy chuyên trách để bồi dưỡng kiến thức cần thiết cho người lao động trước khi đi làm việc ở nước ngoài và hoạt động đưa người lao động đi làm việc ở nước ngoài theo quy định của Bộ Lao động - Thương binh và Xã hội. Trường hợp doanh nghiệp lần đầu tham gia hoạt động đưa người lao động đi làm việc ở nước ngoài thì phải có phương án tổ chức bộ máy chuyên trách để bồi dưỡng kiến thức cần thiết và hoạt động đưa người lao động đi làm việc ở nước ngoài;

3. Người lãnh đạo điều hành hoạt động đưa người lao động đi làm việc ở nước ngoài phải có trình độ từ đại học trở lên, có ít nhất ba năm kinh nghiệm trong lĩnh vực đưa người lao động đi làm việc ở nước ngoài hoặc hoạt động trong lĩnh vực hợp tác và quan hệ quốc tế;

4. Có tiền ký quỹ theo quy định của Chính phủ."

Theo đó, để thành lập công ty về xuất khẩu lao động cần đáp ứng các điều kiện như sau:

- Thứ nhất, doanh nghiệp kinh doanh dịch vụ này phải đáp ứng điều kiện về vốn pháp định: 5 tỷ đồng theo quy định tại Điều 3 Nghị định 126/2007/NĐ-CP;

- Thứ hai, DN phải trực tiếp tổ chức hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài;

- Thứ ba, doanh nghiệp được xem xét cấp Giấy phép hoạt động dịch vụ đưa người lao động đi làm việc ở nước ngoài phải là doanh nghiệp có 100% vốn điều lệ của các tổ chức, cá nhân Việt Nam (Điều 2 Nghị định 126/2007/NĐ-CP);

- Thứ tư, muốn hoạt động dịch vụ này thì DN phải xin giấy phép (phải đáp ứng điều kiện theo quy định tại Điều 9), ngoài ra việc xin giấy phép này còn được hướng dẫn bởi Khoản 2 Mục I Thông tư 21/2007/TT-BLĐTBXH.

Theo quy định thì khi thành lập DN này mình phải đào tạo luôn cả ngoại ngữ cho NLĐ, mình không cần phải xin thêm giấy phép con nhưng trong thành phần hồ sơ xin giấy phép để thực hiện dịch vụ này DN phải cung cấp được danh sách trích ngang cán bộ chuyên trách trong bộ máy hoạt động đưa người lao động đi làm việc ở nước ngoài, gồm các nội dung: họ tên, ngày tháng năm sinh, chức vụ, trình độ chuyên môn, trình độ ngoại ngữ, nhiệm vụ được giao (có giấy tờ, bằng cấp chứng minh khi cơ quan nhà nước có kiểm tra, yêu cầu chứ không phải xin chứng chỉ gì thêm).