This paper on cognitive complexity in primates and cetaceans is a review of studies that use onlyobservational methods. These studies include descriptive accounts, both qualitative and quantitative,of behavior-in-context in naturally-occurring and quasi-experimental settings, especially involvingthe micro-analysis of video. To unify this piecemeal but burgeoning literature, “cognition” is taken asembodied, largely visible, and distributed across physical and social environments. Its study involvesdocumenting the adaptation of behavior to changing conditions, especially in ontogeny, tool-use, andsocial discourse. The studies selected for this review focus on the cognitive complexity that isapparent in the versatility, the hierarchical organization, and the long-term patterning of suchbehavioral adaptations. Versatility is seen, for example, in the substitution of different acts or objectsinto established routines, in the size and flexibility of action repertoires that enable variablyconfigured and sequenced performances, and in the marked occurrence of individual differences.Hierarchical organization is seen in the substitution or iteration of a subroutine that fails to disrupt itslarger routine, in the simultaneous embedding of one social interaction within the frame of another(as in “social tool” use), and in the insertion of a novel or borrowed subroutine as a tactical response,especially one that temporarily redirects an animal‟s trajectory. The complexity apparent in long-termpatterning includes tracking and making selective use of multiple histories (e.g., concerning kinship,rank, etc.) whose predictions and tactics may vary, responding to “market” values that change withecological and social factors, and exploiting traditions of practice which provide social and materialresources that shape engagement and learning. While this literature includes far more primate thancetacean examples, the primate work offers helpful suggestions for settings, issues, and techniquesthat could be adapted to the sensori-motor, ecological, and social constraints on cetacean cognition.The array of observations reviewed illustrate the utility across species of scoring such parameters asdisplays of attention in multiple modalities, abrupt trajectory changes, the complementarity andcontingency of actions, and the resiliency of sequences, to help identify the media that matter in agiven cognitive ecology. Systematic micro-analyses, in conjunction with long-term relational datathat track changes in affordances and coordination, make such observational approaches a viable andvaluable addition to the study of comparative cognition.