Art is a far too complex cultural phenomenon to have been invented ex-nihilo. However, no adequate explanation has so far been given regarding the graphic and cognitive skills which preceded prehistoric art, and made its actual emergence possible. This essay proposes that prehistoric art was preceded by a more primitive kind of pictorial literacy, namely footprints literacy. The obvious attribute common to many early prehistoric paintings and footprints is that both represent their subjects by contour and negative. A deeper analysis of these two kinds of visual literacy reveals many other common attributes: connectivity - differentiation, classification, abstraction, generalization, signification, visual class-names, symmetry - asymmetry, schematization, complementarity, induction, deduction, hypothetical thinking and others. Thus, it is probable that footprints are the proto-symbols from which figurative art evolved. It is striking that the same attributes which appear in footprints literacy and in art, appear much later as basic attributes of modern science, but at a much higher level of sophistication. Possibly, these three domains represent successive stages of noetic evolution. Probably, this finding points to fundamental cognitive attributes or "mindprints" that are basic not only to these areas, but also to human intelligence itself and probably to all other phases of Being. Pointing out the origins of art might be a substantial contribution to the lifting of the veil from the most fundamental attributes of art since its very beginnings. This may provide a new key to the delineation of the demarcation lines between art and non-art, which seems to be the problem that haunts modern art.