What role does the Histadrut play in the lives of Palestinian citizens of Israel employed in the Israeli economy? Much recent scholarship on the Histadrut emphasizes three core elements of the labor union’s status and relation to the Zionist colonial project: first, the Histadrut's role in organizing and incorporating new Jewish immigrants into the economy of the British mandate and, after 1948, of the nascent Israeli state; second, the national labor union’s general decline during the neoliberalization of the Israeli economy from the mid-1970s onward; and third, signs of hopeful revitalization of worker organization (both within and outside of the organizing umbrella of the Histadrut) leading up to and following the 2011 general strike. While the Histadrut has expanded its initially narrow base of support to allow both Palestinian citizens and guest workers (both from the Occupied Palestinian Territories and abroad) to become members, it has done so without abandoning its support for the Zionist colonial-national project. It thus finds itself in the contradictory position of working to defend those very workers whom the Zionist project has colonized, expelled, and exploited while simultaneously viewing itself as a central pillar of this same project. The contradictory role of the Histadrut vis-a-vis Palestinian workers mirrors the contradictory position that those same workers find when laboring within the Israeli economy: Palestinian workers’ labor has built the very economic, infrastructural, and institutional frameworks that the Israeli state has used to further the ethnic cleansing of Palestinian lands, the military rule over the Occupied Palestinian Territories, and the economic, social, and political marginalization of Palestinian citizens of Israel. Through both ethnographic observations within the local Histadrut office in a working-class Palestinian village in Israel and through interviews with union office staff, current unionized members, and former members living in the village, this paper examines how Palestinian-citizen Histadrut members navigate their contradictory roles as Palestinian members of a Zionist labor organization. In doing so, this paper examines the ways in which labor activism is strategically racialized and de-racialized depending on the organizing context; the ways in which colonial racial, ethnic, and gender hierarchies intersect with class hierarchies within Israel’s neoliberal capitalist economy; and the ways in which national labor organizations like the Histadrut can and cannot operate as tools for promoting class solidarity beyond these colonial hierarchies.