Here is a list of the various fish you can find in the game, as well as where they are located. If the fish is necessary for a quest, it will be marked with an * asterisk, as well as in red, like this.
Pacific Saury *
This is one of the first fish you can catch in the game. You can find it on El Dorado's boat, or in the Green Meadows ocean. It's necessary to catch one for the quest Fishing.
