Dating back as far as 100 ka, the Blombos ochre and the Diepkloof ostrich egg engravings are considered among the earliest fossilized evidence of human symbolic behavior. Of special interest to this study is the temporal trajectory spanning more than 30 thousand 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 at each site evolved to become 1) more salient to the human perceptual system, 2) more discriminable from each other, and 3) increasingly associated with symbolic intent. Our findings 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.