Dating back as far as 100 ka, the Blombos ochre and the Diepkloof ostrich egg engravings are considered among theearliest fossilized evidence of human symbolic behavior. Of special interest to this study is the temporal trajectory spanningmore than 30 thousand years from earlier simpler parallel line patterns to later complex cross-hatchings suggesting adaptivecompositional development. Through a series of three psychophysical experiments we test the hypotheses that the line engrav-ings at each site evolved to become 1) more salient to the human perceptual system, 2) more discriminable from each other, and3) increasingly associated with symbolic intent. Our findings suggest that just as instrumental tools have been found to undergocumulative refinements in adaptation to their function, the ochre and egg shell engravings evolved adaptively to become morefit for their cognitive function as signs.