Workflow execution time predictions for Grid infrastructures is of critical importance for optimized workflow executions, advance reservations of resources, and overhead analysis. Predicting workflow execution time is complex due to multeity of workflow structures, involvement of several Grid resources in workflow execution, complex dependencies of workflow activities and dynamic behavior of the Grid. In this paper we present an online workflow execution time prediction system exploiting similarity templates. The workflows are characterized considering the attributes describing their performance at different Grid infrastructural levels. A “supervised exhaustive search” is employed to find suitable templates. We also make a provision of including expert user knowledge about the workflow performance in the procession of our methods. Results for three real world applications are presented to show the effectiveness of our approach.