The earliest record of a European person describing a talking parrot is in Ctesias' Indica. Ctesias was a Greek physician who worked in the court of king Artaxerxes II of Persia in the fifth century BC. He wrote books about his experiences that are known through excerpts and summaries made by later authors, notably Byzantine scholar Photios of Constantinope in the 9th century.

Photius, Excerpt of Ctesias' Indica (Translation J.H. Freese)

of the parrot about as large as a hawk, which has a human tongue and voice, a dark red beak, a black beard, and blue feathers up to the neck, which is red like cinnabar. It speaks Indian like a native, and if taught Greek, speaks Greek.

Ctesias' books have long been ridiculed due to their wild mix of facts and fantasy (monopode people, dog people etc.), but his description of the parrot (and of the elephant) seems grounded in observation. Bigwood (1993) believes that Ctesias' original text was longer and more detailed, and abridged by Photios, who by, the 9th century, may have been well acquainted with parrots. He discusses at length these few lines which seem to be riddled with translation issues. However, the little there is makes it possible to identify the bird as one species of Indian parakeet, possibly Psittacula cyanocephala (Plum-headed Parakeet).

For Bigwood,

it is reasonable to suppose that he is describing a bird which he himself had seen, one perhaps sent as a gift to the Persian king and kept in one of the royal paradeisoi.

Bigwood finds that the assertions about the bird's speaking abilities are a little extravagant ("speaks Indian like a native"), but essentially correct, ie those birds could talk.

A later mention of talking parrots can be found in Aristotle (4th century BC), who may have derived his information from Ctesias:

Aristotle, The History of Animals, Book VIII (Translation D'Arcy Wentworth Thompson)

As a general rule all birds with crooked talons are short-necked, flat-tongued, and disposed to mimicry. The Indian bird, the parrot, which is said to have a man's tongue, answers to this description; and, by the way, after drinking wine, the parrot becomes more saucy than ever.

Arrian of Nicomedia (c. 86/89 – c. after 146/160 AD), in his history of Alexander's conquests, talks about the surprise of Nearchus, an officer of Alexander, at seeing talking birds:

Arrian, The Anabasis of Alexander, Book VIII(Translation E. Iliff Robson, 1933)

But Nearchus describes, as something miraculous, parrots, as being found in India, and describes the parrot, and how it utters a human voice. But I having seen several, and knowing others acquainted with this bird, shall not dilate on them as anything remarkable; nor yet upon the size of the apes, nor the beauty of some Indian apes, and the method of capture. For I should only say what everyone knows, except perhaps that apes are anywhere beautiful.

Bigwood notes that by the time of Arrian, talking parrots were no longer seen as remarkable, since Arrian, with some scorn, declines to reproduce Nearchus' description.

Source Bigwood, J. M. ‘Ctesias’ Parrot’. The Classical Quarterly 43, no. 1 (May 1993): 321–27. https://doi.org/10.1017/S0009838800044396.