Answer: When did octopi start to be?

When Alexis said this was a hard problem, I didn’t realize how hard it was.  It seems there are many answers, and which you believe depends on your reading of the scholarly octopus literature.  (Yes, there is such a thing.) 

[ octopus evolution ] in Google Scholar is tough.  

There ARE lots of papers on the evolution of octopoid eyes (which are strikingly similar to human eyes, an example of convergent evolution), octopus sperm evolution and the development of mimicry as a survival strategy. 

As a consequence, I quickly gave up on Scholar as a resource.  In this case, I don’t know enough evolutionary biology to be able to sort out the wheat from the chaff.  There’s probably a lot of good stuff there, but it’s too highly encoded for me to work with.  (Even after trying [ octopus lineage ] and [ octopus divergence ] which was fascinating, but not helping me out.) 

So I backed up and tried: 

[ octopus diverged ] 

.. .on the open web.  One of the first things I saw was a result from Elsevier.  This is good, as they're a respected scientific publisher, but it's also really annoying, because while they seem to have a few things, they cost $27 to read each article… and this is a fishing expedition!  (I'm not sure who can afford that kind of price.  I doubt that many marine biologists have that kind of money.)  

And after a while I ended up on the Wikipedia article on Mollusca –

“There is good evidence for the appearance of gastropods, cephalopods and bivalves in the Cambrian period 542 to 488.3 million years ago.”  (As differentiated from their non-swimming ancestors, monoplacophoran-like ancestors.  Like half-clams, living on the sea-floor.)    (from  Lemche, H; Wingstrand, K.G. (1959). "The anatomy ofNeopilina galatheae Lemche, 1957 (Mollusca, Tryblidiacea)."Galathea Rep. 3: 9–73)

This is good information, but doesn’t really answer our question:  When did octopus as an independent speicies originate? 

In another article linked from the Wikipedia page we find that “Natilus diverged from octopus around 415M years ago ± 24 million years.”    This, according to:  Bergmann, S.; Lieb, B.; Ruth, P.; Markl, J. (2006). "The hemocyanin from a living fossil, the cephalopod Nautilus pompilius: protein structure, gene organization, and evolution"  Journal of molecular evolution 62 (3): 362–374.

Given this as a start, I got to be curious about the vampyromorphs (apparently the octopus’s closest relatives) and my query became:

[ octopus vampyromorph divergence ]

Big point:  When doing complex research tasks like this, you often learn a great deal about the domain.  This is an important aspect of research-search, one that we need to pay attention to  (and we will, in a later post--stay tuned).  

Which me to all of the following resources…. There was so much of it, and it was SO confusing, I started taking notes from the resources I found most interesting.  

Part of the confusion stems from the many different senses of “evolve” or “diverge” or “speciate.”  In most cases you have to read really carefully to figure out which species is being discussed, and which speciation event they’re talking about.  

If ever there was a time and place for careful reading, THIS is it.  I found it very easy to be reading along, and only later realize that I was reading about the divergence between subspecies of octopi.  Careful! 

Some of the more interesting pages I found…

http://www.thecephalopodpage.org/evolution.php

Octopuses diverged from the vampyromorphs during the Late Jurassic (about 140 million years ago) as far as we can tell—but the fossil record is too patchy to make this estimate anything more than provisional. In some ways octopuses can be thought of as vampyromorphs that have lost their shells more or less completely. Comparisons of the mitochondrial DNA of various types of living cephalopod also seems to support a closer relationship between the octopuses and vampyromorphs that either has with the squids, spirulas or cuttlefishes. Of the two octopods groups—the Cirrata and the Incirrata—it isn't at all obvious which gave rise to which, and why the octopuses lost their shells so completely is obscure.

{ This is  the cephalopod web site of James Wood, who has a PhD in biology, with extensive experience in marine biology research.  Wood is also associated with CephBase, a database of cephalopod data. } 

http://www.tonmo.com/science/fossils/fossiloctopuses.php

The most likely scenario seems to be that during the Late Devonian (480 – 360 Mya) the first octopods stemmed from the primitive vampyromorphs almost losing any trace of an internal shell by the time of our first fossil, Pohlsepia.

{ An octopus hobbyist online magazine, but with a staff of people who actually work in marine biology, with affiliations like UC Berkeley and the Monterey Bay Aquarium.} 

http://onlinelibrary.wiley.com/doi/10.1111/j.1096-0031.2006.00086.x/abstract
Divergence time estimates for major cephalopod groups: evidence from multiple genes, (J. Strugnell,  J. Jackson, A. Drummond, A Cooper; Cladistics Volume 22, Issue 1, pages 89–96, February 2006) where they say…

The data support a Paleozoic origin of the Orders Vampyromorpha, Octopoda and the majority of the extant higher level decapodiform taxa. These estimated divergence times are considerably older than paleontological estimates. The major lineages within the Order Octopoda were estimated to have diverged in the Mesozoic, with a radiation of many taxa around the Cretaceous/Cenozoic boundary. 

SUMMARY: 

Strugnell – Paleozoic: 541 – 251 Mya

Tonmo – Late Devonian:  480 – 360 Mya

Cephalopod Page (Wood) – Jurassic: 140 Mya

Bergmann – 415 Mya

Lemche - 542  - 488.3 Mya

So... four reputable sources agree--the Ocotopi seem to have emerged as a separate, identifiable species around 400 Mya.  As often happens with these studies, it's rare to get a clear, neat date for such events.   We gather the data as best we can, and then see what the consensus is.  In any case, it's worth nothing that the genus Homo didn't appear until around 0.2 Mya... just to keep things in perspective.  

Search on!  (You've got another 0.0001 Mya to go!)