The use of Cloud infrastructures together with provisioning technologies can be successfully applied in scenarios where resources are only needed rarely and irregularly, for example simulation workflows in the eScience domain. There has already been proposed a solution for the on-demand provisioning of services required by workflows, but how to automatically provision the needed workflow middleware itself is still an open issue. Although many provisioning technologies are available, it is currently not possible to use them in an integrated, flexible and automated way. The main idea presented in this paper is a multistep bootstrapping process, starting with a minimal local software component and ending up with a complex workflow middleware running in the Cloud. This minimal software component is called bootware. We define the key requirements for the bootware, present its architecture and discuss the main design decisions and how they fulfil the requirements. The bootware enables to provision complex workflow middleware systems on-demand and automatically in the Cloud and therefore reduces resource consumption and costs.