Over the last several decades, transportation scientists have made substantial progress in identifying and tackling transport-related problems by elaborating sophisticated policy instruments. Originally, the policy instruments were developed and designed to tackle inefficiencies caused by conventional (human-driven) vehicles. However, questions remain regarding transportation policies, especially pricing instruments, in the future. With the advent of fully autonomous vehicles (driverless or self-driving cars), many of potentially disruptive changes to our transportation system are projected to occur. This gives rise to the question of how to adapt the existing, well established, policy instruments to make them applicable to a world of self-driving cars. The present paper utilizes one of the most widely deployed, most important (in terms of tax revenue), and most effective (in terms of carbon dioxide mitigation) current price-based policy instruments in the transport sector (i.e., the energy tax) to show how one of the most innovative features associated with fully autonomous vehicles (i.e., driverless vehicle relocation) affects the optimal design of a transportation tax. We adopt a microeconomics optimization framework and analytically derive the optimal energy tax under the assumption that driverless vehicle relocation is possible. Our main finding is that in a world of self-driving cars, the energy tax (likewise, a second-best miles tax) as a price-based policy instrument becomes more difficult to evaluate. With the capability of fully autonomous vehicles to relocate without passengers inside, the (analytical) expression for the optimal energy tax becomes more complex, and its (numerical) determination becomes more difficult since the feature of driverless vehicle repositioning imposes counteracting welfare effects as a response to a tax change. Policymakers and researches are encouraged to take on the challenge of increasing complexity to tackle transport-related inefficiencies in the era of self-driving cars.