As Al Pemberton recalls, it was about three years after the Red Lake Band of Chippewa and the Minnesota Department of Natural Resources signed an agreement to restore walleye populations in Upper and Lower Red lakes that he saw the true potential for the big lakes’ recovery.

The agreement, which state and tribal officials had signed on a perfect afternoon in April 1999, resulted from the collapse of the walleye population in Minnesota’s largest inland lake, a once-unthinkable outcome caused by years of overfishing...