The unit's history began on 17 September 1943 at Camp Peary, Virginia, where it was commissioned as the 133rd Naval Construction Battalion (NCB).

After 7 months of training at Davisville, Gulfport and Port Hueneme the battalion's first overseas assignment was NAS Honolulu, Territory of Hawaii (May–October 1944).

Before joining the 4th at Camp Maui, the 133rd was put through the Army's Pacific Jungle Combat Training Center (CTC) at Punaluu and Kahana Valleys on the North Shore of Oahu, TH.

The history is, that "on the beach at Iwo, bulldozers proved to be worth their weights in Gold"[9] and the CBs had the biggest and the best the Navy could provide.

Each shore party had Marine JASCO (Joint Assault Communications Co) men attached as well as personnel from the 442nd U.S. Army Port Company.

The corpsman, security sections, equipment operators and truck drivers were on call at all times, from the beginning to the end of the assault.

[32] The USMC ground commanders felt every man that set foot on the island during the assault should get a Presidential Unit Citation or PUC.

Fox Annex to the 4th Marine Division's Operations Report, of April 1945, shows 133's Companies individually tasked to "assault" infantry battalions.

[44] In October some of 133's men went with the 31st CB to Sasebo, Japan for the occupation reconstruction (and were discharged at Bremerton Naval Yard, in Washington state January 1946).

(most CBs created a new insignia when they were recommissioned) After completion of training in Gulfport and Camp Lejeune they deployed to Đà Nẵng East, Vietnam.

A large project that time was the repair of the 286-foot center span of the main highway bridge damaged during the Tet Offensive.

The battalion, along with NMCB 128, provided material support to NMCBs 1 and 11 while they repaired the bridge at Bau Phu on Route 1.

It deployed to Okinawa with detachments to: Guam, Biên Hòa Air Base, Vietnam, Azores and the Aleutians.

From Okinawa they had detachments to Iwakuni, Japan, Oahu, Hawaii, Biên Hòa, Vietnam and Subic Bay, P.I.

[60] NMCB 133's base was established in a walled compound called Camp Sommers along with the headquarters of the 24th Marine Expeditionary Unit (MEU) and the 18th Engineer Brigade.

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.

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.

[62] In March 1998 the battalion sent a Det of 217 men back to Bosnia to build SEAHuts and do bridge repair work.

[63] On 28 November 2001 the first members of NMCB 133 arrived at Camp Rhino, Afghanistan as part of Operation Enduring Freedom.

[65] January and February 2003 saw the battalion deployed in support of the 1st Marine Expeditionary Force operationally assigned to the 1st MEF Engineer Group.

[66] 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.

The battalion worked in support of Combined Joint Task Force – Horn of Africa (CJTF-HOA) building schools in remote villages and making potable water available to the people.

NMCB 133 also had a presence in São Tomé, working with Underwater Construction Team ONE (UCT 1) in the reconstruction the Coast Guard only boat launch.

"NMCB 133's Seabees built the foundation for new buildings on White Beach Naval Facility in Okinawa and restored running water to a village in Malaysia that been without this basic life necessity for over three years.

Within a month, a fully operational Seabee camp was built and with the Army a power generating supply was set up.

[66] The list of tasks completed by the Seabees of 133 includes: In October 2010, NMCB 133 received the Atlantic Fleet Best of Type Battle "E" award for its work during the CENTCOM deployment.

The mission was site preparation near Monrovia Airport for a dozen or medical facilities to be built by the U.S. military's Operation United Assistance to deal with the Ebola crisis in West Africa.

[67][68] In August 2017, the wreck of the USS Baltimore was located by the Hawaii Undersea Research Laboratory (HURL) south of Oahu.