Cephalopods preserve very badly due to their body structure, but we're pretty sure they've been around since the Cambrian. They really took of in the Ordovician, reaching forms several metres long.
However, the more intelligent cephalopods are thought to have developed this intelligence as a result of competition with Mesozoic marine reptiles. They haven't changed much since at least the Cretaceous (see http://en.wikipedia.org/wiki/Keuppia ) but are probably more intelligent now than ever before, due to the greater diversity of sea life now than ever in the past (though it is declining). HolbenilordTalk₪ 22:57, November 13, 2011 (UTC)