A major challenge for European governments is solving the dilemma of increasing security and control of international trade, while at the same time reducing the administrative overhead carried by commercial and public administration organisations. Electronic Customs, the transformation of paper-based trade documents to electronic ones, and the corresponding redesign of customs procedures, seems to be very promising approach to deal with this dilemma. However, while ICT is widely perceived as a key component of a solution, we argue in this paper that the complexity of the redesign of these electronic documents and procedures for international trade is far more problematic than traditional business process and network innovations. We identify key challenges facing the development and introduction of innovative eCustoms solutions and we outline conceptual and methodological approaches to address these challenges. In such a way, we outline a research approach for eCustoms innovation and transformation.