A new approach for the limit analysis of masonry vaults retrofitted with fiber-reinforced polymers (FRP) based on an upper bound formulation is presented in this paper. In particular, a new genetic algorithm (GA)-nonuniform rational b-spline (NURBS)-based general framework for the limit analysis of curved masonry structures tailored upon an upper bound formulation is discussed thoroughly in the present Part I. A given FRP-reinforced masonry vault can be geometrically represented by a NURBS parametric surface, and a NURBS mesh of the given surface can be generated. Each element of the mesh is a NURBS surface itself and can be idealized as a rigid body. An upper bound limit analysis formulation, which takes into account the main characteristics of masonry material and FRP reinforcement, is deduced, with internal dissipation allowed exclusively along element interfaces. The approach is capable of well predicting the load-bearing capacity of any reinforced masonry vault of arbitrary shape, provided that the initial mesh is adaptively adjusted by means of a metaheuristic approach (i.e., a suitable GA) to enforce that element edges accurately approximate the actual failure mechanism. The approach is validated and discussed in Part II, which is devoted to presenting a number of structural analyses of FRP-reinforced vaults.