Author summary: Intelligent behavior encompasses appropriate navigation in complex environments that is achieved through the integration of sensorial information and memory of past events to create purposeful movement. This behavior is often described as “complex”, but universal ways to quantify such a notion do not exist. Promising candidates for measures of functional complexity are based on information theory, but fail to take into account the important role that memory plays in complex navigation. Here, we study a different information-theoretic measure called “integrated information”, and investigate its ability to reflect the complexity of navigation that uses both sensory data and memory. We suggest that measures based on the integrated-information concept correlate better with fitness than other standard measures when memory evolves as a key element in navigation strategy, but perform as well as more standard information processing measures if the robots navigate using a purely reactive sensor-motor loop. We conclude that the integration of information that emanates from the sensorial data stream with some (short-term) memory of past events is crucial to complex and intelligent behavior and speculate that integrated information–to the extent that it can be measured and computed–might best reflect the complexity of animal behavior, including that of humans.