Dating back as far as 100 ka, the Blombos ochre and the Diepkloof ostrich egg engravings are considered among the earliest fossil evidence of human symbolic behavior. The engravings found on the same sites spanOf special interest to this study is the temporal trajectory spanning more than 50 k years from earlier simpler parallel line patterns to later complex cross-hatchings suggesting adaptive compositional development. Through a series of three psychophysical experiments we test the hypotheses that the line engravings 1) evolved to become more salient to the human perceptual system, 2) more discriminable from each other, and 3) increasingly associated with symbolic intent. Our finding suggest that just as instrumental tools have been found to undergo cumulative refinements in adaptation to their function, the ochre and egg shell engravings evolved adaptively to become more fit for their cognitive function as signs.