Democracy is not an absorbing state; transitions to autocratic rule have been frequent throughout history and often followed periods of instability under democratic rule. In this paper, we ask whether autocrats can win support among voters by showcasing their ability to restore order and to “get things done.” We analyze a famous case – the building of the highway network in Nazi Germany. Highway construction began shortly after Hitler became Chancellor, and was one of the regime’s signature projects. Using newly collected data, we show that highway construction was highly effective in boosting popular support, helping to entrench the Nazi dictatorship. These effects are unlikely to reflect direct economic benefits. Instead, highway construction signaled economic “competence” and an end to austerity, so that many Germans credited the Nazi regime for the economic recovery. In line with this interpretation, we show that support for the Nazis increased particularly strongly where highway construction coincided with greater radio availability – a major source of propaganda. The effect of highways was also significantly stronger in politically unstable states of the Weimar Republic. Our results suggest that infrastructure spending can win “hearts” for autocracy when “minds” are led to associate it with visible economic progress and an end to political instability.