Mechanisms of avian navigation have received considerable attention, but whether different navigational strategies are accompanied by different flight characteristics is unknown. Managing energy expenditure is critical for survival, therefore understanding how flight characteristics, and hence energy allocation, potentially change with birds familiarity with a navigational task could provide key insights into the costs of orientation. We addressed this question by examining changes in wingbeat characteristics and airspeed of homing pigeons (Columba livia) as they learned a homing task. Twenty-one pigeons were released 20 times individually from either 3.85 km or 7.06 km from home. Birds were equipped with 5 Hz GPS trackers and 200 Hz tri-axial accelerometers. We found that, as the birds' route efficiency increased during the first six releases, their median peak-to-peak dorsal body (DB) acceleration and median DB amplitude also increased. This, in turn, led to higher airspeeds, suggesting that birds fly slower when traversing unfamiliar terrain. By contrast, after route efficiency stabilised, birds exhibited increasing wingbeat frequencies, which did not result in further increases in speed. Overall, higher wind support was also associated with lower wingbeat frequencies and with increased DB amplitude. Our study suggests that the cost of early flights from an unfamiliar location may be higher than subsequent flights both due to inefficient routes (increased distance) and lower airspeeds (increased time). Furthermore, the results indicate, for the first time, that birds modulate their wingbeat characteristics as a function of navigational knowledge, and suggest that flight characteristics may be used as "signatures" of birds' route familiarity.