Cheers went up when Colville tribal fisherman Mylan Williams hauled a 20-pound chinook out of the Columbia River with a dip net. Then hats came off in a show of respect. Tribal elders circled the fish and sang, honoring the salmon that gave up its life to feed the people.

For thousands of years, ancestors of the Confederated Tribes of the Colville Reservation have performed First Salmon ceremonies on the banks of the Columbia. But in recent decades, only a few fish have returned. The tribe recently celebrated the opening of a $50 million hatchery designed to bolster runs to the Upper Columbia and a tributary, the Okanogan River...