Determining the genetic pathways that viruses traverse to establish in new host species is crucial to predict the outcome of cross-species transmission but poorly understood for most host-virus systems. Using sequences encoding 78% of the rabies virus genome, we explored the extent repeatability and dynamic outcome of evolution associated with multiple host shifts among New World bats. Episodic bursts of positive selection were detected in several viral proteins, including regions associated with host cell interaction and viral replication. Host shifts involved unique sets of substitutions, and few sites exhibited repeated evolution across adaptation to many bat species, suggesting diverse genetic determinants over host range. Combining these results with genetic reconstructions of the demographic histories of individual viral lineages revealed that although rabies viruses shared consistent three-stage processes of emergence in each new bat species, host shifts involving greater numbers of positively selected substitutions had longer delays between cross-species transmission and enzootic viral establishment. Our results point to multiple evolutionary routes to host establishment in a zoonotic RNA virus that may influence the speed of viral emergence.