Η πρώτη αναφορά που συναντάμε σε ιστορικό κείμενο για τα Κοτύωρα είναι στο έργο του Ξενοφώντα «Κύρου Ανάβασις», όταν ο στρατηγός και συγγραφέας διέμεινε στο στρατόπεδο των Μυρίων για 45 μέρες μέχρι να έρθουν τα πλοία που θα τους πήγαιναν πρώτα στην Ηράκλεια του Πόντου και έπειτα στην Ελλάδα (Ξενοφών, χ.χ). Στο διάστημα αυτό ο Ξενοφών καταγράφει μία ιστορική μαρτυρία, που, αν και δε μας δίνει ακριβείς πληροφορίες για το πότε ιδρύθηκαν τα Κοτύωρα, γνωστοποιεί ότι πρόκειται για πόλη που αποικήθηκε από Έλληνες της Σινώπης:
«Ἐν τούτῳ ἔρχονται ἐκ Σινώπης πρέσβεις, φοβούμενοι περὶ τῶν Κοτυωριτῶν τῆς τε πόλεως (ἦν γὰρ ἐκείνων καὶ φόρον ἐκείνοις ἔφερον) καὶ περὶ τῆς χώρας, ὅτι ἤκουον δῃουμένην. καὶ ἐλθόντες εἰς τὸ στρατόπεδον ἔλεγον· προηγόρει δὲ Ἑκατώνυμος δεινὸς νομιζόμενος εἶναι λέγειν· Ἔπεμψεν ἡμᾶς, ὦ ἄνδρες στρατιῶται, ἡ τῶν Σινωπέων πόλις ἐπαινέσοντάς τε ὑμᾶς ὅτι νικᾶτε Ἕλληνες ὄντες βαρβάρους, ἔπειτα δὲ καὶ ξυνησθησομένους ὅτι διὰ πολλῶν τε καὶ δεινῶν, ὡς ἡμεῖς ἠκούσαμεν, πραγμάτων σεσωσμένοι πάρεστε. ἀξιοῦμεν δὲ Ἕλληνες ὄντες καὶ αὐτοὶ ὑφ᾽ ὑμῶν ὄντων Ἑλλήνων ἀγαθὸν μέν τι πάσχειν, κακὸν δὲ μηδέν· οὐδὲ γὰρ ἡμεῖς ὑμᾶς οὐδὲν πώποτε ὑπήρξαμεν κακῶς ποιοῦντες. Κοτυωρῖται δὲ οὗτοι εἰσὶ μὲν ἡμέτεροι ἄποικοι, καὶ τὴν χώραν ἡμεῖς αὐτοῖς ταύτην παραδεδώκαμεν βαρβάρους ἀφελόμενοι· διὸ καὶ δασμὸν ἡμῖν φέρουσιν οὗτοι τεταγμένον καὶ Κερασούντιοι καὶ Τραπεζούντιοι· ὥστε ὅ τι ἂν τούτους κακὸν ποιήσητε ἡ Σινωπέων πόλις νομίζει πάσχειν».
«Γι’ αυτό το λόγο ήρθε από τη Σινώπη πρεσβεία αντιπροσώπων, που ανησυχούσε για την τύχη των Κοτυώρων και των γύρω περιοχών μιας και τους απέδιδαν φόρο υποτέλειας, επειδή είχε διαδοθεί ότι κινδυνεύουν από εχθρικές επιδρομές. Στρατιώτες, είμαστε απεσταλμένοι από την πόλη της Σινώπης και μάθαμε ότι νικάτε και αντιμετωπίζετε με επιτυχία τις επιδρομές των βαρβάρων, γι’ αυτό και ήρθαμε πρωτίστως να σας επαινέσουμε που πολεμάτε σαν γενναίοι Έλληνες και, έπειτα, να σας συγχαρούμε γιατί παρόλο που περάσατε πολλά δεινά, βρίσκεστε σώοι και αβλαβείς μαζί μας. Αξιώνουμε, λοιπόν, επειδή αμφότεροι είμαστε Έλληνες να επιδιώκετε όσα είναι ωφέλιμα για το κοινό καλό και όχι όσα θα μας ζημιώσουν. Εξάλλου, από μέρους μας δεν υπήρξε ποτέ ως τώρα κακή μεταχείριση σε βάρος σας. Οι Κοτυωρίτες είναι δικοί μας άποικοι και αυτήν εδώ τη χώρα την παραδώσαμε σ’ αυτούς, αφού πρώτα την είχαμε απελευθερώσει από τους βαρβάρους. Γι’ αυτό το λόγο άλλωστε είναι υποχρεωμένοι να μας πληρώνουν φόρους, όπως ακριβώς πράττουν, αντίστοιχα, οι Κερασούντιοι και οι Τραπεζούντιοι Έτσι, λοιπόν, διατρανώνουμε ότι θα μας βρει απέναντι οποιοσδήποτε έχει σκοπό να τους βλάψει, γιατί θεωρούμε ότι τα δικά τους συμφέροντα είναι και δικά μας».
Ο Εκατώνυμος, στο εν λόγω χωρίο, μιλά στο στρατόπεδο των Μυρίων ως αντιπρόσωπος της πρεσβείας που εστάλη από τη Σινώπη προς στήριξη των Κοτυωριτών και με το λόγο του μας δίνει την πληροφορία ότι τα Κοτύωρα ήταν πόλη που απελευθερώθηκε από τους βάρβαρους χάρη στη συνδρομή των Σινωπέων, γι’ αυτό και έκτοτε πλήρωνε τακτικά φόρους στη μητρόπολη Σινώπη, όπως ακριβώς συνέβη, επίσης, με την περίπτωση των Κερασούντιων και των Τραπεζούντιων (Ξενοφών, χ.χ.).
Το πότε ιδρύθηκαν τα Κοτύωρα παραμένει ασαφές και μπορούμε να το υποθέσουμε μόνο κατά προσέγγιση. Γνωρίζοντας ότι οι Έλληνες της Σινώπης πρώτα ίδρυσαν ελληνική αποικία στην Τραπεζούντα το 756 π.Χ. και στη συνέχεια έκαναν το ίδιο με την Κερασούντα και τα Κοτύωρα, η χρονολογία ίδρυσης των Κοτυώρων ανάγεται μεταξύ 750 π.Χ. και 400 π.Χ. (Σαλτσής, 1955).