The Albany Photo-Engravers Union No. 21 was chartered in 1921 as an affiliate of the International Photo Engravers Union of North America (IPEUNA). Local 59 of the Amalgamated Lithographers of America (ALA) was chartered in 1943 with a single shop and approximately 50 members.[GCIU, Local 259-M. Dinner Journal (20th Anniversary of Local 59), [1963]] In 1964 IPEUNA and ALA merged at the international level to form the Lithographers and Photoengravers International Union (LPIU). Local 59-L merged with the Albany Photo-Engravers Union No. 21-P, LPIU, to form Local 259 in 1966. [GCIU Local 259-M. Dinner Journal, 1966] With the merger of LPIU and the International Brotherhood of Bookbinders (IBB) in 1972, the local became Local 259-M (signifying "Merged") of the Graphic Arts International Union (GAIU). In 1983 the GAIU merged with the International Printing and Graphic Communications Union (IPGCU), Local 259 became an affiliate of the Graphic Communications International (GCIU). In 1987, the Utica Graphic Communications Union, Local 58-C (signifying "Commercial") merged into Local 259-M.

The Utica Graphic Communications Union, Local 58-C, was chartered in 1898 as Utica Printing Pressmen's Local 58 of the International Printing Pressmen and Assistants' Union of North America (IPPAU). When the IPPAU merged with the International Stereotypers', Electrotypers', and Platemakers' Union of North America (ISE&PU) in 1973, the local became Utica Printing and Graphic Communications Union No. 58 of the International Printing and Graphic Communications Union (IPGCU). When the IPGCU merged with the GAIU to form the Graphic Communications International Union in 1983, the local became the Utica Graphic Communications Union No. 58-C.[Fink Gary, ed. Labor Unions. Westport, Conn.: Greenwood Press, 1977, pp. 137-39, 300-04]

Local 58 was involved in a prolonged strike against the Utica Observer-Dispatch that involved four other unions. The strike was begun on July 15, 1967, by Local 58 when it disagreed with the newspaper over how many people were needed to tend a new press. The Utica Newspaper Guild No. 129; Stereotypers', Electrotypers', and Platemakers' Union, Local 46; and the Lithographers and Photoengravers International Union, Local 61, joined the strike afterwards. The Utica Typographical Union No. 62 observed the picket lines but never joined the strike. The five unions formed a joint committee during the strike and bargained with management together, although the Utica Typographical Union was the leader in economic negotiations.[The Guild Reporter, October 27, 1967, pp. 1 and 6] After 100 days, the unions received an improvement in wages that was also sought, and the strike (the longest in Utica's history) ended.

GAIU, Local 259-M, was involved in a noteworthy case against the Amsterdam Printing and Litho Corporation. The union had lost an National Labor Relations Board election in 1973, but it objected to the conduct of Amsterdam Printing and Litho during the election and another election was held. Local 259-M won that election and was certified as the bargaining agent for all lithographic production employees in the plant. The company refused to recognize the union and eliminated a Christmas bonus, changed wages, and reduced the workweek for its employees, all without consulting with the union. In 1976, the company was determined by NLRB to be engaging in unfair labor practices and was ordered to restore the workweek, pay all lost bonuses, pay for wages lost, and pay for the wages of laid-off employees up to the time the company began bargaining in good faith with the union. All these payments included interest. [GCIU Local 259-M. Subject Files. "Amsterdam Printing and Litho Corp.--Litigation over Refusal to Recognize Union--Folder 2, 1973-77."]