On the Klamath River in northern California, Karuk tribal fishermen traditionally provide salmon for food and ceremonies, yet the region has sustained serious environmental degradation in recent years. What happens to Karuk masculinity when there are no fish? Using interviews and public testimony, the authors examine how declining salmon runs affect the gender identities and practices of Karuk fishermen. Gendered practices associated with fishing serve ecological functions, perpetuate culture in the face of structural genocide, and unite families and communities. The authors find that the absence of fish resulting from ecological damage affects both food availability and the quality of social connections, which in turn affects individual gender practices and symbolizes genocide to the community. Karuk men’s individual struggles to construct themselves as men are thus interwoven with struggles against racism and ongoing colonialism. The authors coin the term colonial ecological violence to describe these circumstances. They also describe how some men restructure masculine identities by transferring “traditional” cultural responsibilities to fish, community, and “collective continuance” to new settings as activists and fishery scientists. The authors call for a decolonized sociology that uses more theorizing of the particular and very real ways ecological relationships structure gender in traditional Native communities to understand the operation of gendered and racialized colonial violence in the form of environmental degradation, today.