Abstract: In the process of GIS service chaining, the quality of service (QoS), as well as functionality of service, is very essential for Web GIS users. Nevertheless, OGC standards for GIS services have not yet supported QoS currently. This paper proposes a QoS extension to OGC interoperation specifications related to GIS services as well as an optimal approach of GIS web service chaining with global QoS constraints. This constrained optimization question is solved using a genetic algorithm with a penalty-based fitness function and a tree coding structure modeling the flowchart of GIS service chaining. With an experimental example, the effectiveness of this approach is verified in comparison with Integer programming method. By changing examination conditions such as the number of candidate services or task nodes, it is found that this approach has near linear time complexity.