Aerial vehicles have recently attracted significant attention in a variety of commercial and civilian applications due to their high mobility, flexible deployment and cost-effectiveness. To leverage these promising features, the aerial users have to satisfy two critical requirements: First, they have to maintain a reliable communication link to the ground base stations (GBSs) throughout their flights, to support command and control data flows. Second, the aerial vehicles have to minimize their propulsion power consumption to remain functional until the end of their mission. In this paper, we study the trajectory optimization problem for an aerial user flying over an area including a set of GBSs. The objective of this problem is to find the trajectory of the aerial user so that the total propulsion-related power consumption of the aerial user is minimized while a cellular-connectivity constraint is satisfied. This problem is a non-convex mixed integer non-linear problem and hence, it is challenging to find the solution. To deal with, first, the problem is relaxed and reformulated to a more mathematically tractable form. Then, using successive convex approximation (SCA) technique, an iterative algorithm is proposed to convert the problem into a sequence of convex problems which can be solved efficiently.