Homing pigeons (Columba livia) are believed to adopt a map-and-compass strategy to find their way home. Surprisingly, to date a clear demonstration of the use of a cognitive map in free-flight experiments is missing. In this study, we investigated whether homing pigeons use a mental map in which - at an unknown release site - their own position, the home loft and a food loft are represented simultaneously. In order to test this, homing pigeons were trained to fly to a 25-30 km distant food loft. A total of 131 hungry and satiated pigeons were then released from an unfamiliar site equidistant from the food loft and the home loft. Their vanishing bearings and homing times were assessed conventionally at four sites, and also their flight tracks from one release site by means of GPS loggers. The vanishing bearings of fed and hungry birds differed significantly at all release sites and a highly significant proportion of hungry birds flew to the food loft, while the fed birds headed home. The GPS experiment revealed a number of pigeons flying very precisely to the food loft, others correcting their flight direction after topography-induced detours. This implies that the pigeons knew their geographical position in relation to the targets, and chose a flight direction according to their locally manipulated needs - clearly the essence of a cognitive navigational map.