Significance The production of purposely made painted or engraved designs on cave walls is recognized as a major cognitive step in human evolution, considered exclusive to modern humans. Here we present the first known example of an abstract pattern engraved by Neanderthals, from Gorham’s Cave in Gibraltar. It consists of a deeply impressed cross-hatching carved into the bedrock of the cave older than 39 cal kyr. The engraving was made before the accumulation of Mousterian layer IV. Most of the lines composing the design were made by repeatedly and carefully passing a pointed lithic tool into the grooves, excluding the possibility of an unintentional or utilitarian origin. This discovery demonstrates the Neanderthals’ capacity for abstract thought and expression.