At least it was the case of Tianyuan 1, a Paleolithic individual from Northern China who lived some 40,000 years ago. Isotope analysis from the teeth show that this person was a regular consumer of fish. This finding determines that ancient humans had the ability of fishing on regular basis at least as early as that date.
Yaowu Hu et al., Stable isotope dietary analysis of the Tianyuan 1 early modern human. PNAS, 2009. Open access.
Divulgative article also at Science Daily.
Ezana at Anthropology Forum points me to another older evidence of coastal food-gathering habits: Eritrea c. 125,000 years ago:
Robert C. Walter et al., Early human occupation of the Red Sea coast of Eritrea during the last interglacial. Nature, 2000. It's behind a paywall but you can access the tables and figures freely.
A divulgative article can be found here.
It seems that there is a lot of evidence accumulating in favor of early humans using the coastal landscape quite naturally. This, of course, supports the coastal migration model.