Octopuses have large brains and exhibit complex behaviors, but relatively little is known about their cognitive abilities. Here we present data from a five-level learning and problem-solving experiment. Seven octopuses (Octopus vulgaris) were first trained to open an L shaped container to retrieve food (level 0). After learning the initial task all animals followed the same experimental protocol, first they had to retrieve this L shaped container, presented at the same orientation, through a tight fitting hole in a clear Perspex partition (level 1). This required the octopuses to perform both pull and release or push actions. After reaching criterion the animals advanced to the next stage of the test, which would be a different consistent orientation of the object (level 2) at the start of the trial, an opaque barrier (level 3) or a random orientation of the object (level 4). All octopuses were successful in reaching criterion in all levels of the task. At the onset of each new level the performance of the animals dropped, shown as an increase in working times. However, they adapted quickly so that overall working times were not significantly different between levels. Our findings indicate that octopuses show behavioral flexibility by quickly adapting to a change in a task. This can be compared to tests in other species where subjects had to conduct actions comprised of a set of motor actions that cannot be understood by a simple learning rule alone.