The Columbia River Fishermen's Beneficial Aid Society was organized on August 16, 1875; it was incorporated on March 3, 1876. The Society’s main purposes were to establish rules regarding the drifting grounds and boundaries for Columbia River gillnet fishermen and to establish insurance so that the widows of fishermen who died as a result of their occupation would receive a death benefit. In July 1879, the Society was renamed the Columbia River Fisherman's Protective Union (CRFPU) and was incorporated as an association of Columbia River gillnetters only. Other fisheries on the river included trap and seine operations.

The CRFPU pushed for higher prices for fish and worked on issues of safety, navigation, and the conservation of salmon. On April 17, 1880, the Daily Astorian printed this notice: "We, the undersigned fishermen of the Columbia River Fishermen's Protective Union hereby pledge ourselves not to fish for less than sixty (60) cents per fish, and if any one of the members of this union be discharged on account of this resolution, we all agree to leave in a body. We also request every fisherman on this river to follow our example." The notice was signed by more than 400 fishermen. The union also built a steam snag scow, the Pathfinder, to pull debris from the river bottom that could entangle and damage nets.

In 1886, the union allied with the American Federation of Labor. At all of the canneries along the Columbia, the union had representatives whose job it was to sign up members and represent them at union meetings. In the small fishing communities along the lower Columbia, immigrants spoke a variety of languages, including Croatian, Finnish, Norwegian, Italian, Swedish, Danish, Greek and German. There were few roads, and nearly all transportation between communities was by water. With no telephones and few newspapers, CRFPU representatives were frequently a major source of information about the wider world.

In 1896, the CRFPU led a bitter strike against the Columbia River packers to try to get a higher price for fish. Before the strike was over, the National Guard in Oregon and Washington was called out. Fishermen finally settled for four and a half cents per pound. Once the fishers were back at work, however, the packers reduced the price to two cents per pound and put a 500-pound daily limit on each boat. In response, 200 fishermen pooled their resources and formed the Union Fishermen's Cooperative Packing Company. The coop was highly successful and lasted into the late 1940s, when it was sold.

The CRFPU faced a multitude of environmental challenges during the twentieth century. There were ongoing struggles over the construction of main stem Columbia River dams, irrigation ditch gates, hatcheries and the artificial propagation of salmon, and industrial pollution. In the 1930s, the union initiated the first significant legal actions against pollution in the river and lobbied heavily for clean water legislation. The union’s actions eventually led to stricter water pollution controls throughout Oregon. From the mid-twentieth century on, withstanding increased pressure from recreational fisheries occupied a prominent place in the organization's activities, as evidenced by the many legislative bills and initiative petitions designed to reduce or eliminate gillnetting on the Columbia.

The Union's board of directors is drawn from different fishing districts along the Columbia, with an executive secretary in the leadership role. Executive secretaries have included Sofus Jensen, Henry Niemela, Bob Hicks, Charles Henne, William Westerholm, Russell Bristow, William Puustinen, Ross Lindstrom, and Jack Marincovich. Currently, the CRFPU operates out of its office at the Port of Astoria and conducts a recycling program for used fishing gear. The union's publication, The Gillnetter, is a compendium of current and historical information and photographs.