Prior to 20th century depletion of fishing stocks from over fishing, herring was a major food fish of the North Sea. Huge fishing fleets set out to catch this significant food source to feed northern Europe. Herring in particular do not keep well without refrigeration - within 24 hours they begin to deteriorate. To preserve the fish, herring were salt cured for 24 hours, then smoked on spits in chimneys for up to 48 hours. In this process, the herring turned dark red and stiff as a board. These red herrings could now be kept safely for long periods of time, requiring soaking in fresh water for softening and desalination before cooking.
Red herring were a staple in the diet of the poor, hence their contribution to the idiom neither fish nor fowl nor good red herring. Red herring were also incredibly redolent, resulting in their use, noted elsewhere, in distracting hounds from the trail of a fox.