This site gives 1674 as the first appearance in print of the saying, from a treatise called "An Account of the Voyage to New England." But I imagine it goes back well before that.

And the same site gives two different views about whether it's true or not. "I've been assured by my various biologist friends that the first thing that starts to disintegrate in a fish is the brain." " says one. But there's a quote from a "fish pathologist" who says "It's biologically incorrect. When a fish rots, the organs in the gut go first."

Anyway, if it's been round since 1674, that's good enough for me.