A possible contender for the oldest is found in Russian folklore, where there is the Samosek Sword. The Encyclopedia of Russian & Slavic Myth and Legend (accessed 9/12/2018) mentions it under three different entry headings: Ivan the Guard (p.126-128), Nemal Chelovek (p.203-204), Samosek Sword (p.248-249).
The Nemal Chelovek entry contains relevant information (somewhat paralleled in both the other entries) as to the sentience of the sword (bold and italics added):
Just then Nemal Chelovek returned to his
mansion and stormed into the great hall
where Ivan was standing with the princess.
When the sorcerer saw Ivan, he cast a spell
that made him grow until his head brushed
the ceiling, and then he rushed at Ivan. Ivan
simply lifted the Samosek Sword, which flew
through the air of its own volition and neatly
decapitated the oncoming giant. Then the
sword went through the mansion and killed
all of Nemal Chelovek’s servants before
returning neatly to Ivan’s hand. Ivan and the
princess then went home, and no one in the
world was ever troubled again by Nemal
So the sword has its own volition, and enough sentience to go "through the mansion" itself and slay all the servants.
A variation of the story is found in the Wikipedia article for "Dragon," under the "Eastern Europe" heading as well (accessed 9/12/2018; bold added):
In Russian and Ukrainian folklore, Zmey Gorynych is a dragon with three heads, each one bearing twin goat-like horns. He is said to have breathed fire and smelled of sulfur. It was believed that eclipses were caused by Gorynych temporarily swallowing the sun. According to one legend, Gorynych's uncle was the evil sorcerer Nemal Chelovek, who abducted the daughter of the tsar and imprisoned her in his castle in the Ural Mountains. Many knights tried to free her, but all of them were killed by Gorynych's fire. Then a palace guard in Moscow named Ivan Tsarevich overheard two crows talking about the princess. He went to the tsar, who gave him a magic sword, and snuck into the castle. When Chelovek attacked Ivan in the form of a giant, the sword flew from Ivan's hand unbidden and killed him. Then the sword cut off all three of Gorynych's heads at once. Ivan brought the princess back to the tsar, who declared Ivan a nobleman and allowed him to marry the princess.
For more information, though not as clear on sentience, see: Wikipedia Sword Kladenets (Samosek subentry, the term mech-samosek meaning "the self-swung sword").
But what I have not yet been able to find definitively is a date for the earliest known telling of this sword's story. So at present, I cannot verify it is older than the 16th c. The Ruyi Jingu Bang answer. However, it is noted to be part of Russian mythology, which redirects on Wikipedia to Slavic paganism, which begins:
Slavic paganism or Slavic religion define the religious beliefs, godlores and ritual practices of the Slavs before the formal Christianisation of their ruling elites. The latter occurred at various stages between the 8th and the 13th century.
So if this story is indeed pre-Christian, and the latter occurred in stages from 8th-13th centuries, then it seems possible the story is pre. 8th c. (and at least likely prior to the 12th c. of the other answer). But until I can find verification of earliest known date of the story, I cannot verify.*
*If anyone can find a source for the dating of this story, I would greatly appreciate it.