To clarify, the sapience of the being or species must be undetermined and uncertain to the reader and the characters in the story at first. Accusing a clearly sapient being of not being sapient does not count unless the sapience of said being has to be proven for legal purposes and the claim is made in court.
1726: In Part 4 of Gulliver's Travels by Jonathan Swift, Gulliver is shipwrecked on an island where the dominant people are super-rational horses, the Houyhnhnms. Much of this part of the book is occupied by the Houyhnhnms' incomprehension at Gulliver's account of European civilization, as they can see no rational purpose behind having lawyers, wine, money, fashion, etc. Equally, Gulliver is initially confused by the Houyhnhnms, thinking them to be ordinary horses (but very curious ones), before he is able to teach himself their language and understand that they are the ones in charge of the island. The place is also peopled by the bestial Yahoos, who are basically humans without the veneer of civilization, and are regarded as mere animals. Gulliver is initially classified as a Yahoo, and later comes to accept the label since he perceives why the Houyhnhnms can't see a difference between the Yahoos of their island, and the court of Queen Anne (the encounter takes place in 1710-1715, so she was still alive for Gulliver). The Houyhnhnms eventually exile him without having accepted him as a fully rational being.
For the present question, the true sapience of the Houyhnhnms is concealed from the reader at their first appearance, and Gulliver of course does not realize. They also doubt him, and his decree of exile came about after their nearest equivalent of "the sapience of said being has to be proven for legal purposes and the claim is made in court"; they have a quadrennial council which issues exhortations as to what they decide is the most rational course of action, and it is this council which decides Gulliver is far below their standards of rationality.
First encounter with a Houyhnhnm, in chapter 1 of part 4:
But looking on my left hand, I saw a horse walking softly in the field; which my persecutors having sooner discovered, was the cause of their flight. The horse started a little, when he came near me, but soon recovering himself, looked full in my face with manifest tokens of wonder; he viewed my hands and feet, walking round me several times. I would have pursued my journey, but he placed himself directly in the way, yet looking with a very mild aspect, never offering the least violence. We stood gazing at each other for some time; at last I took the boldness to reach my hand towards his neck with a design to stroke it, using the common style and whistle of jockeys, when they are going to handle a strange horse. But this animal seemed to receive my civilities with disdain, shook his head, and bent his brows, softly raising up his right fore-foot to remove my hand. Then he neighed three or four times, but in so different a cadence, that I almost began to think he was speaking to himself, in some language of his own. [...] I was amazed to see such actions and behaviour in brute beasts; and concluded with myself, that if the inhabitants of this country were endued with a proportionable degree of reason, they must needs be the wisest people upon earth.
Gulliver then guesses they might be transformed magicians, but does not follow up on this conjecture; he thinks they are most likely to be highly trained horses. He tries to imitate some of the horse-sounds they are making, in particular the utterances "Yahoo" and "Houyhnhnm", without understanding what they might mean. In Chapter 2, they reach a dwelling place and Gulliver still expects to see a human master:
But, that a man of quality should be served all by horses, was beyond my comprehension. I feared my brain was disturbed by my sufferings and misfortunes.
and he expects
that a people who could so far civilize brute animals, must needs excel in wisdom all the nations of the world.
By this point, matters are probably clear enough for the reader, but Gulliver doesn't quite get it until Chapter 3. He is by then able to pick up much more of their language, and becomes convinced of their superiority. For their part, the Houyhnhnms still treat him as
a wonderful Yahoo, that could speak like a Houyhnhnm, and seemed, in his words and actions, to discover some glimmerings of reason.
Even after several years, he is only ranked as having (Chapter 9)
all the qualities of a Yahoo, only a little more civilized by some tincture of reason, which, however, was in a degree as far inferior to the Houyhnhnm race, as the Yahoos of their country were to me.
As their consensus is still that he only has "some rudiments of reason" (Chapter 10), they decide that he must sail or swim home.
Murphy said doubtfully, "Then they’re intelligent.”
"No, not necessarily. After all, wasps build complicated nests with no more equipment than a set of instincts.”
"What’s your opinion?” asked Damon. "Just what impression does it give?”
Fletcher shook his head. "I can’t be sure. I don't know' what kind of standards to apply. ’Intelligence’ is a word that means lots of different things, and the way we generally use it is artificial and specialized.”
"I don’t get you,” said Murphy.
"Do you mean these deks are intelligent or don’t you?”
Fletcher laughed. "Are men intelligent?"
"Sure. So they say, at least.”
"Well, what I’m trying to get across is that we can’t use man’s intelligence as a measure of the dekabrach’s mind. We’ve got to judge him by a different set of values — dekabrach values. Men use tools of metal, ceramic, fiber: inorganic stuff — at least, dead. I can imagine a civilization dependent upon living tools — specialized creatures the master-group uses for special purposes. Suppose the dekabrachs live on this basis? They force the coral to grow in the shape they want. They use the monitors for derricks or hoists, or snares, or to grab at something in the upper air.”
"Apparently, then,” said Damon, "you believe that the dekabrachs are intelligent.”
Fletcher shook his head. "Intelligence is just a word — a matter of definition. What the deks do may not be susceptible to human definition.”
"It’s beyond me,” said Murphy, settling back in his chair.
Damon pressed the subject. "I am not a metaphysicist or a semanticist. But it seems that we might apply, or try to apply, a crucial test.”
"What difference does it make one way or the other?” asked Murphy.
Fletcher said, "It makes a big difference where the law is concerned.”
"Ah,” said Murphy, "the Doctrine of Responsibility.”
Fletcher nodded. "We could be yanked off the planet for injuring or killing intelligent autochthones. It's been done.”
"That’s right,” said Murphy. "I was on Alkaid Two when Graviton Corporation got in that kind of trouble.”
"So if the deks are intelligent, we've got to watch our .step. That’s why I looked twice when I saw the dek in the tank.”
"Well — are they or aren’t they?” asked Mahlberg.
"There’s one crucial test,” Damon repeated.
The crew looked at him expectantly.
"Well?” asked Murphy. "Spill it.”
1954: Heinlein's The Star Beast. A plot twist occurs when the titular 'Star Beast', "Lummox", a pet of the main (human) character, grows arms and hands (a natural stage of her development, but one she has taken many years (decades?) to achieve), qualifying her as sapient under a "speaks and has hands" rule of thumb.
This new status saves her from the threat of imminent execution (for destruction of property, being a menace, etc.).
From the Internet Archive:
Look — do you remember the Cygnus Decision?”
“The Cygnus Decision? We had it in elementary Customs of Civilization?”
“Yes. Quote it.”
“What is this? A mid-semester quiz?” John Thomas frowned and dug into his memory. “ ‘Beings possessed of speech and manipulation must be presumed to be sentient and therefore to have innate human rights, unless conclusively proved otherwise.’ ” He sat up. “Hey! They can’t kill Lummox — he’s got hands!”
(Lummox already speaks but by growing hands is now 'possessed of manipulation'. Her gender is established a little later in the book)
For what it's worth, this is essentially the opposite of the Little Fuzzy plot twist — in that story, the fuzzies are known to be expert manipulators but are revealed at the end of the novel to have (ultrasonic) language [as well as being able to make fire], which satisfies the "speak and build a fire" rule prevalent in that society ...
1962: This is the plot of H. Beam Piper’s Little Fuzzy - a potentially sapient species is discovered on a planet effective owned by a company which is exploiting its natural resources; if the species is found sapient, the planet’s status will change to protect them and the company will lose its exploitative charter.
A. E. van Vogt's Black Destroyer short story, published in 1939 and later merged with several other stories into the fix-up novel The Voyage of the Space Beagle. The Coeurl is first thought by the human explorers to be a highly intelligent animal, and later turns out to be a survivor of the civilization that built the abandoned cities found on the planet where it was discovered.