Các bước xử lý:

1. Đương sự làm đơn cớ mất hộ chiếu với công an địa phương nơi mất hộ chiếu hoặc nơi đăng ký tạm  trú. Trong đơn nêu rõ tên tuổi, quốc tịch, số hộ chiếu, ngày cấp, nơi cấp, cơ quan cấp thị thực. Công an địa phương xác nhận việc cớ mất.
2. Đến cơ quan đại diện lãnh sự của quốc gia đương sự mang quốc tịch xin cấp giấy thông hành, giấy đi đường hoặc hộ chiếu mới.
3. Cơ quan đại diện lãnh sự có công hàm thông báo hủy hộ chiếu đã mất, đề nghị các cơ quan chức năng Việt Nam cấp lại thị thực xuất cảnh cho đương sự.
4. Sở Ngoại vụ TP. Hồ Chí Minh chuyển công hàm trên cho Cục Quản lý Xuất nhập cảnh – Bộ Công an  thông báo việc hủy hộ chiếu cũ đã bị mất và đề nghị cấp lại thị thực cho đương sự xuất cảnh.
5. Đương sự nộp hồ sơ (công hàm của cơ quan đại diện lãnh sự, công văn của Sở Ngoại vụ TP. Hồ Chí Minh, đơn cớ mất có xác nhận của Công an địa phương và giấy thông hành) cho Cục Quản lý Xuất nhập cảnh – Bộ Công an, kèm theo bản khai theo mẫu của Bộ Công an.  
6. Cục Quản lý Xuất nhập cảnh – Bộ Công an sẽ xem xét giải quyết.
7. Trường hợp không có cơ quan đại diện lãnh sự tại Thành phố Hồ Chí Minh đương sự phải xin thông hành (hoặc hộ chiếu) tại cơ quan đại diện ngoại giao (Đại sứ quán) ở Hà Nội. Nếu không có Đại diện tại Việt Nam, đương  sự phải liên lạc với Cơ quan đại diện ngoại giao của họ tại nước thứ ba để xin các giấy tờ cần thiết nói trên.

Cơ sở pháp lý:

1. Pháp lệnh Nhập cảnh, Xuất cảnh và Cư trú của người nước ngoài tại Việt Nam ngày 12-05-2000.
2. Nghị định số 21/CP ngày 28-05-2001 của Chính phủ hướng dẫn thi hành Pháp lệnh về Nhập cảnh, Xuất cảnh và Cư trú của người nước ngoài tại Việt Nam.
3. Thông tư liên tịch số 04/2002/TTLT/BCA-BNG ngày 29-01-2002 giữa Bộ Công an và Bộ Ngoại giao hướng dẫn thi hành Nghị định 21/CP và Pháp lệnh Nhập cảnh, Xuất cảnh và Cư trú của người nước ngoài tại Việt Nam.