Combat Logistics Battalion 31 (CLB-31) was activated in June 1979 at Kaneohe Bay, Hawaii, as Logistic Support Unit 31, 31st Marine Amphibious Unit, Fleet Marine Forces Pacific. The unit was re-designated October 1979 as Marine Amphibious Unit Service Support Group 31 (MSSG-31), 31st Marine Amphibious Unit (31st MAU). The unit was deactivated in April 1985. In September 1992, the unit was reactivated as Marine Expeditionary Unit Service Support Group 31 (MSSG-31) operationally controlled by the reactivated 31st Marine Expeditionary Unit (MEU).

From its time of reactivation to 1998, MSSG-31 supported the 31st MEU in various theater exercises in the Pacific region such as VALIANT USHER, COBRA GOLD, and FOAL EAGLE. In December 1998, 31st MEU was the theater reserve for OPERATION DESERT FOX where it conducted a non-combatant evacuation of 90 American citizens from Kuwait. In January 2000, MSSG-31 was part of the Special-Purpose Marine Air-Ground Task Force (SPMAGTF) East Timor supporting the Australian-led International Forces in East Timor to the new United Nations Transitional Administration East Timor. From September 2004 to March 2005, MSSG-31 supported Battalion Landing Team 1st Battalion 3rd Marines during combat operation in support of Operation IRAQI FREEDOM participating in Operation PHANTHOM FURY. In January 2006, MSSG-31 supported humanitarian relief efforts in Leyte, Philippines.

In October 2006, MSSG-31 was re-designated to its current moniker CLB-31. From May to June of 2008, CLB-31 responded to the post-cyclone relief efforts in Myanmar in Operation CARING RESPONSE. In 2010, CLB-31 provided disaster relief to Luzon, Philippines after Super Typhoon Megi. Then in 2011, while conducting an exercise in Malaysia, CLB-31 participated in Operation TOMODACHI in the relief efforts after the earthquake and tsunami that devastated Oshima Island, Japan.

In August 2015, elements of CLB-31 were redirected from an exercise in vicinity of Guam and Palau in order to perform Defense Support of Civilian Authorities (DSCA) operations, providing disaster relief to the island of Saipan following Typhoon Soudelor. While in Saipan, the battalion used organic water production equipment to produce 279,375 gallons of water. Combined with the water production capabilities of the USS Ashland (LSD-48), the battalion distributed a total of 366,200 gallons of potable water to the population of Saipan. In support of the Federal Emergency Management Agency (FEMA), the American Red Cross, and other non-governmental organizations (NGO's), the battalion distributed 255 pallets of supplies, consisting of 47,040 meals, 16,625 gallons of packaged water, and additional supplies. The battalion ensured the uninterrupted operation of the island's emergency services communication network by delivering power generation to the communications tower at the highest point on the island.

CLB-31 recently completed the 31st MEU Summer Deployment 17.2 in September 2017. This deployment included the multinational exercise TALISMAN SABER in Australia, where the 31st MEU participated in an amphibious landing and conducted follow-on operations ashore alongside the US Navy, US Army, Royal Australian Army, and Royal Australian Navy.