This article analyzes how to use IT to deploy trust-based regulation in the government-to-business (G2B) relationship, with the Authorized Economic Operator (AEO) certification in the Netherlands between the Tax and Customs administrations and the businesses as a case study. Specifically, based on the theory of institutional economics, the article discusses how to implement the AEO by utilizing the modern ICT, at lower transaction costs, in the meanwhile enhancing the trust and reputation between the government and businesses. We illustrate the benefits of trust-based regulation by presenting a qualitative comparison of the transaction costs under the two different types of regulations (control-based vs. trust-based). Further, with the AEO case study, we emphasize on the role of IT in facilitating this trust-based regulation design, in following three perspectives: competence trust signaling, competence trust screening, and goodwill trust enhancing. The article concludes with policy recommendations on how to further improve trust-based regulations (in our case, the AEO certification) by enhancing the reputation effect of the regulation in four aspects, which are influenced by the popularity, reliability, effectives and international recognition of the policy. Governments should strongly promote AEO certification in order to exploit the network externalities and make it a worldwide standard. © 2011 .