In 1997 Kaiser Permanente (KP) and a coalition of 26 local unions representing nearly 70,000 Kaiser employees created what is now the nation's largest and most ambitious labor-management partnership. In 2000, the parties faced the major challenge of negotiating their first labor agreement under the new Partnership. They designed and implemented what is also the largest and most complex interest-based negotiations (IBN) process carried out to date in the field of labor-management relations. We describe this case here, both to provide an historical account of the process and to explore the lessons that might be learned from how these parties addressed a series of generic challenges encountered when introducing IBN principles into collective bargaining