In March 1991 the battalion deployed to Spain and was ordered to send its AirDet to Zakho, Iraq, on 1 April. Three weeks later on the 22nd orders came to recall all detachments and for the main body to redeploy to Zakho as a component of Operation Provide Comfort. This took the battalion to Iraq assigned to the Army's 18th Engineer Brigade. When the Main Body mounted out of Rota its equipment was sent by sea to Iskenderum, Turkey. From there it was convoyed 400 miles to Zakho, Iraq. NMCB 133's base was established in a walled compound called Camp Sommers with the headquarters of the 24th Marine Expeditionary Unit (MEU) and the 18th Engineer Brigade. Operation Provide Comfort had two Joint Task Forces with JTF Bravo headed by the 24th MEU. Due to the amount of work they were tasked with, the battalion went to 12-hour days. It was an emergency service relief effort that originally was thought would take 3 months. However, due to the large number of Kurds returning home from the refugee-displaced person camps, 133 was able leave after 8 weeks. December 1995 into 1996, in support of the Implementation Force (IFOR) code named Operation Joint Endeavour an Air Det Heavy of 170 men deployed to the Sava River crossing at Zupanja, Croatia. There they constructed the first and very urgently needed displaced persons tent camp of the Implementation Force. Renovation of the NATO Commander's facilities in Sarajevo was one project. Detail Juliet Echo was assigned the construction of camps for the US Army's 16th Corps Support Group in Croatia and the 1st Armored Division's Ready 1st Combat Team in Bosnia.  1997 Korean Air Lines flight 801 crashed in the jungles of Guam and 133 helped get ground access to the site. In March 1998 the battalion sent a Det of 217 men back to Bosnia to build SEAHuts and do bridge repair work. On 28 November 2001 the first members of NMCB 133 arrived at Camp Rhino, Afghanistan as part of Operation Enduring Freedom. During this deployment it was decided to make Camp X-Ray operational again and 133 sent the battalion's detail at Roosevelt Roads to Guantanamo Bay to make it happen. January and February 2003 saw the battalion deployed in support of the 1st Marine Expeditionary Force operationally assigned to the 1st MEF Engineer Group. In Southern Iraq the battalion created a POW facility for 14,000, provided defense for 2 bridges and maintenance to the main supply routes as part of Task Force Charlie.