In this work, we present an iterative learning strategy and experimental validation thereof for optimizing the flight trajectory of an underwater kite. The methodology is adapted to two different power generation configurations. The iterative learning algorithm consists of two main steps, which are executed at each iteration. In the first step, a meta-model is updated using a recursive least squares (RLS) estimate to capture an economic performance index as a function of a set of basis parameters that define the flight trajectory. The second step is an iterative learning update using information from past cycles to update basis parameters at future cycles using a gradient ascent formulation. This algorithm was experimentally validated on a scaled experimental prototype underwater kite system towed behind a test vessel in Lake Norman, North Carolina. Using our experimental system and algorithm, we were able to increase the kite’s mechanical power generation by an average of 24.4% across the tests performed.