The epigraphical material from Apollonia Pontica provides a valuable opportunity to analyze the presence and acculturation of non-Greek individuals in the Milesian colony during the relatively early period of the 5th century BC. How do we measure the extent to which they are others? By scrutinizing and comparing the archaeological, epigraphic, and onomastic evidence about Greeks and non-Greeks in the colony with those of other cities in the Aegean area in the Classical Period, the paper provides a plausible reconstruction of the colonization process and the social structure of the town and also tries to define the methodological principles that should be applied in research of this kind.