Form I-131, Application for Travel Document - to obtain permission to depart the US and to return while the application for adjustment of status remains pending.
All of the applications must be completed and submitted with supporting documentation (i.e. birth certificate of the foreign national resident applicant translated into English if need be, evidence of the termination of all prior relationships for both of you (again translated if needed), evidence of the petitioning spouse's immigration status in the US, copies of passport information, tax returns and evidence of current income). These applications are all processed through the National Benefits Center, a USCIS Service Center which is located in Missouri but whose "lockbox" filing location is in Chicago. Generally, a medical examination on Form I-693 must also be provided at the time of initial submission of the paperwork to USCIS.
When the applications are received, filing receipts are issued and sent to you and your spouse. She will be contacted for an appointment to appear at a local Application Support Center where her "biometrics" will be captured (digital photo, digital signature and digital fingerprints). Eventually, an interview will be scheduled before an Immigration Services Officer at the nearest CIS Field Office. At this interview, the applications will be reviewed and the government will ask for you and your spouse to provide documentary evidence that your relationship is a bona fide marriage and not a relationship entered for the sole purpose of evading the immigration laws.
Currently, the average processing time for these applications is less than 6 months in just about each one of the CIS Field Offices throughout the US. Some applications take longer to process than others and others take less time to be processed. Keep in mind that each case is its own entity and past successes are never an indication of future success. Each case is reviewed on its own merits and as time ensues, the background checks that are completed prior to the approval of a case become more comprehensive. USCIS is certainly doing a lot more today to make sure that its decision are sound than it was doing the year previously and certainly much more than it was when I first started handling these cases.