We estimate demand for automobiles in Greece using a discrete choice model of product differentiation and use the model to evaluate carbon-based tax schemes that could shift consumer purchases towards low-CO2 cars and thus lead to the reduction of fuel use and CO2 emissions. We find that careful policy design, supported by appropriate modeling, can bring about substantial environmental benefits without losing control of economic parameters such as public finances or firm profits. This finding comes in contrast to the results of recent vehicle tax reforms in European countries, which turned out to be more costly than initially expected. Our analysis indicates that, especially in countries with already heavy vehicle taxation, improper implementation of carbon-based taxes can have adverse unintended environmental consequences.