We propose a stochastic model of language evolution that permits both homoplasy and non-tree evolution (so as to reflect borrowing between lineages). We discuss the issues involved in reconstructing evolutionary histories under the model, specifically showing that the tree component of the model is identifiable, that efficient methods exist for reconstructing the tree, and that full likelihoods can be calculated in linear time. We conclude with a discussion of data selection and analysis, and compare our stochastic model for language evolution to existing models in molecular evolution.