There has been much debate regarding the internal history of the Tukanoan languages during the last four decades, with different classification proposals being based on lexical and phonological data. Here, we present a new classification of the Tukanoan language family based on an improved computational approach which infers phylogenetic trees from proposed sound change patterns. In contrast to traditional methods based on the manual identification of shared innovations by experts, our method identifies valid innovations within a parsimony framework. In contrast to existing computational models which are mostly based on binary character states for lexical data, we model sound change patterns as directed weighted transitions between multiple character states. We apply the new approach to a set of 21 extant Tukano languages. Our results confirm the east-west split of the Tukanoan languages which was proposed in the past and suggest a classification which groups Kubeo with Tanimuka on the one hand, and Koreguahe with Maihiki, on the other hand, thus reconciling previous classifications. We use this new classification to propose a consensus phylogeny of Tukanoan in which all automatically inferred shared innovations were manually checked and uncertainties are explicitly displayed.