This is the context:
12 One of the Cretans, a prophet of their own, said, “Cretans are always liars, evil beasts, lazy gluttons.” 13 This testimony is true. Therefore rebuke them sharply, that they may be sound in the faith, 14 not devoting themselves to Jewish myths and the commands of people who turn away from the truth. 15 To the pure, all things are pure, but to the defiled and unbelieving, nothing is pure; but both their minds and their consciences are defiled. 16 They profess to know God, but they deny him by their works. They are detestable, disobedient, unfit for any good work. (ESV)
To some extent this is tongue in cheek, since Paul naturally expected that not just Titus, but all the church in Gortyna, and all the elders in other churches in Crete would see the letter and take it as partly humorous. Yet it also has a theological background which Cretan readers would recognise:
Epimenides (6th-century BC). In his Cretica it was denying the immortality of Zeus which was the lie of the Cretans.
They fashioned a tomb for thee, O holy and high one
The Cretans, always liars, evil beasts, idle bellies!
But thou art not dead: thou livest and abidest forever,
For in thee we live and move and have our being. (Epimenides, Cretica)
The phrase “Cretans, always liars” was quoted by other poets with the same content regarding Zeus:
O Zeus, some say that thou wert born on the hills of Ida;
Others, O Zeus, say in Arcadia;
Did these or those, O Father lie? — “Cretans are ever liars.”
Yea, a tomb, O Lord, for thee the Cretans builded;
But thou didst not die, for thou art for ever. (Callimachus, Hymn I to Zeus)