Rapid technological advances in transcriptomics and lineage tracing technologies provide new opportunities to understand organismal development at the single-cell level. Building on these advances, various computational methods have been proposed to infer developmental trajectories and to predict cell fate. These methods have unveiled previously uncharacterized transitional cell types and differentiation processes. Importantly, the ability to recover cell states and trajectories has been evolving hand-in-hand with new technologies and diverse experimental designs; more recent methods can capture complex trajectory topologies and infer short- and long-term cell fate dynamics. Here, we summarize and categorize the most recent and popular computational approaches for trajectory inference based on the information they leverage and describe future challenges and opportunities for the development of new methods for reconstructing differentiation trajectories and inferring cell fates.