Time critical grid applications as for example simulations for medical surgery or disaster recovery have special Quality of Service requirements. The Vienna Grid Environment, developed and evaluated in the context of the EU Project GEMSS, facilitates the provision of HPC applications as QoS-aware Grid services by providing support for dynamic negotiation of various QoS guarantees like required execution time and price. In this paper, we extend the QoS mechanisms offered by the Vienna Grid Environment to workflow applications. We describe QoS extensions of the Business Process Execution Language and present a first prototype of a corresponding QoS-aware workflow engine which implements different strategies in order to bind the tasks of a workflow to adequate Grid services subject to user-specified QoS constraints. We present different Grid workflow planning approaches as well as first experimental results.