If you don't limit the definition of "ocean seafood" in OP to the solid and in form strictly, the garum, fish source made from sea fishes caught in the Mediterranean, could be transported by the river networks in the Roman Empire about 2,000 years ago (1th and 2th centuries CE), and pottery vase called amphorae used for the vessel of fish sauce as well as the development of zooarchaeology in identifying fish bones of sea fishes has also recently helped us with the provenance of the fish source.
To give some examples, two archaeological evidence (samples of fish bones) respectively found in Salzburg (now Austria) and Mainz (Germany) testify the presence of sardine-based fish sauce (in the former case) and the marine mackerel specie (from Iberian Peninsula) in the latter city around the 1th century CE (van Neer 2010: 163). Typological analysis of the amphorae also suggest that the amphorae made in Baetica (now NE Spain) and Gallia Narbonensis (southern France) were mainly used for the export of the garum product from the Mediterranean. Bone remains of Spanish mackerel are also found and identified across the northern part of Empire around 0 CE to the 2th century CE sporadically (Van Neer 2010: 168f., Table 1).
+++
As for the existence/ degree of the commercial fishery in the northern seas (the North Sea and the Baltic) before the 12th century, researchers have still discussed, but you can at least also see the outline of the Norwegian stockfish export to Continental Europe in the Later Middle Ages in my previous post in: How did the people of the past dry and store fish and other foods?
(Adds): While not mentioning how they were transported to the inland market, /u/LXT130J's posts in: In medieval films, barrels and wooden crates seem to be a ubiquitous "filler" prop. How common would it actually have been to transport or store goods in such containers en masse in the European Middle Ages? also offer us some ideas on the scale of the commercial herring fishery as well as processing in the Later Middle Ages.
References:
You may be interested in this answer from u/gothwalk, which discusses the Anglo-Saxon Fish Event Horizon.
Drying, salting and pickling fish has a considerably longer history than frozen fish. I can't say what the logistical limitations of transporting fish inland were, but shelf life would not have been a limiting factor for seafood processed in that way.
My knowledge is limited to method used historically in Northern Europe so that's where my focus will be.
One of the oldest methods of preserving fish was to soak it in brine and hang it out to dry, producing what is called Stockfish.
This method was and remains popular in Norway and Iceland, where fish species like cod, haddock and wolffish are plentiful, insects are few and the climate is cool and windy allowing for rapid drying. In Iceland the Westfjords region was preferred for its relatively low humidity and a large number of windswept peninsulas.
The fish in question is gutted and cleaned, and then left out to dry. Once dry, the fish will remain edible for a few years if properly stored (I personally have some year old stockfish in my fridge which I recently ate with no ill effect).
This method of drying fish is very old. It is mentioned here in chapter 17 of Egil's saga, written around the year 1200. The following quotation refers to a voyage that took place in the 9th century AD:
Thorolf had this ship made ready, and put aboard some of his house-carles as crew; he freighted it with dried fish and hides, and ermine and gray furs too in abundance, and other peltry such as he had gotten from the fell; it was a most valuable cargo. This ship he bade sail westwards for England to buy him clothes and other supplies that he needed; and they, first steering southwards along the coast, then stretching across the main, came to England. There they found a good market, laded the ship with wheat and honey and wine and clothes, and sailing back in autumn with a fair wind came to Hordaland.
More pertinent to your question though, I discovered a source as I was writing this comment which mentions stockfish was traded inside Iceland as far inland as 50 kilometers from the coast. A considerable distance at the time given how slow travel was at the time, fresh fish would undoubtedly not have survived the journey except perhaps in the winter.
A more recent method of preserving fish in Northern Europe is drying and salting. This method is more recent as salt was historically rather expensive in Northern Europe and the method demands substantially more salt than making stockfish.
Dried and salted cod in particular, became a major export product in Iceland in the 19th century. The codfish is beheaded and gutted, cleaned. It is then left in a tub of salt for a few days. Then the fish is spread out on bare rocks and allowed to dry in the sun and wind as shown here on this picture from 19th century Reykjavik. The cod was then shipped to markets in various Mediterranean countries.
Then of course, there is pickling. Pickled herring is a European delicacy that dates to the medieval period. Multiple countries caught it and it was a commonly traded food. Countries around the Baltic sea in particular produced pickled herring for export to countries in Western Europe.
