Primates and other animals must detect novel objects. However, the neuronal mechanisms of novelty detection remain unclear. Prominent theories propose that visual object novelty is either derived from the computation of recency (how long ago a stimulus was experienced) or is a form of sensory surprise (stimulus unpredictability). Here, we use high-channel electrophysiology in primates to show that in many primate prefrontal, temporal, and subcortical brain areas, object novelty detection is intertwined with the computations of recency and sensory surprise. Also, distinct circuits could be engaged by expected versus unexpected sensory surprise. Finally, we studied neuronal novelty-to-familiarity transformations during learning across many days. We found a diversity of timescales in neurons’ learning rates and between-session forgetting rates, both within and across brain areas, that are well suited to support flexible behavior and learning in response to novelty. Our findings show that novelty sensitivity arises on multiple timescales across single neurons due to diverse but related computations of sensory surprise and recency and shed light on the computational underpinnings of novelty detection in the primate brain.