Understanding phenotypic disparity across the tree of life requires identifying where and when evolutionary rates change on phylogeny. A primary methodological challenge in macroevolution is therefore to develop methods for accurate inference of among-lineage variation in rates of phenotypic evolution. Here, we describe a method for inferring among-lineage evolutionary rate heterogeneity in both continuous and discrete traits. The method assumes that the present-day distribution of a trait is shaped by a variable-rate process arising from a mixture of constant-rate processes and uses a single-pass tree traversal algorithm to estimate branch-specific evolutionary rates. By employing dynamic programming optimization techniques and approximate maximum likelihood estimators where appropriate, our method permits rapid exploration of the tempo and mode of phenotypic evolution. Simulations indicate that the method reconstructs rates of trait evolution with high accuracy. Application of the method to datasets on squamate reptile reproduction and turtle body size recovers patterns of rate heterogeneity identified by previous studies but with computational costs reduced by many orders of magnitude. Our results expand the set of tools available for detecting macroevolutionary rate heterogeneity and point to the utility of fast, approximate methods for studying large scale biodiversity dynamics.