The main contribution of this paper is an efficient shape optimization algorithm for complex concrete arch dam based on shape sensitivity formulations for design-dependent loads, such as body forces, surface tractions and earthquake loadings. In literature the applied forces are often assumed to be conservative or design-independent. However, in shape design problems applied loads are often functions of design variables. Also, for practical shape definition in the optimisation of large arch dams, a high number of design variables and numerous non-linear constraints are needed. Therefore, for efficient sensitivity design, the concept of mesh design velocity of finite element nodes is employed. It also enables a fast estimation of the gradients needed for each optimisation cycle. The relevant optimisation sub-problem is solved with the SQP method. These procedures have been implemented in a special purpose software, along with an efficient definition of seismic loads suitable for optimisation purposes. The method is successfully applied to an existing Iranian arch dam, and has enabled a dramatic reduction of computational efforts when compared to classical methods.