With the advance of electronic business relationships over the internet, the linking of cross-organizational business processes in virtual supply chains and other scenarios is rapidly increasing. Existing standards for the interoperability of information systems on the business process level are being adapted to suit the needs of the Internet economy. Especially the use of XML as a domain-independent encoding standard for business documents has led to the development of business frameworks such as BizTalk or open/EDI, and interoperability mechanisms that support these standards are being developed. In this paper we describe an architecture for the support of cross-organizational workflows through XML messages. This architecture has been implemented and tested within the AFRICA project at the University of Muenster, Germany. While our work is based upon the emerging Wf-XML standard of the Workflow Management Coalition, it contains a number of significant enhancements that provide a secure, reliable management of global workflow processes.