Governments around the world identify the advancement of electronic invoicing in businesses as crucial for tackling administrative burdens. This paper examines, for the first time, the potential cost savings of e-invoicing in Belgium. Our analysis shows that the total cost of invoicing for Belgian private sector businesses in 2014 amounted to €3.47 billion (0.96% of GDP) and could be reduced to €1.46 billion (0.38% of GDP) if all invoices were sent digitally. Furthermore, an analysis of both barriers and enablers of e-invoicing reveals significant concerns that remain regarding the safety of e-invoicing, although a majority of private sector businesses clearly identifies the potential efficiency gains. From our contingent valuation survey among 683 Belgian businesses, we learn that the average willingness to pay (WTP) for the required investments for implementing digital invoicing amounts to €2,380. However, the potential annual cost savings of digital invoicing for the average small business in our sample is over €7,000. Additionally, our linear regression models indicate that the WTP is positively impacted by the perceived time and reduced risk gains of digital invoicing.