Recent work has shown that when an aircraft encounters ambient ice-supersaturated conditions (where contrails may form and persist), it may be possible to avoid contrail formation by shifting cruise altitude up or down 2000 feet. If an aircraft's cruise altitude is shifted from the optimal profile during a portion of the mission, fuel consumption increases. Because on average approximately 20% of distance flown by commercial airliners is through ice-supersaturated regions, this study quantifies the fuel burn penalties for the notional scenario of flying the same fraction of cruise at altitude displacements of +2000, -2000, and -4000 ft. Present aircraft performance data was used to generate accurate fuel burn penalty estimates.This study finds that the net penalties for existing aircraft to fly contrail avoidance shifts vary between 0.2% and 0.7% increase in block fuel consumption. The magnitude of the fuel penalty can be reduced by approximately 0.25% by slowing down during the shifted segment. Further reductions are attainable for future aircraft with application of engine and aerodynamic technology intended to improve off-design performance. This suggests that if contrail regions could be predicted prior to flight planning, the fuel burn penalties for avoiding contrails over a single mission may be relatively small. However, implementation of this type of contrail avoidance system requires considerable advancements in the prediction of ice-supersaturated regions. Moreover, the fuel burn penalties realized in practical application of this system are likely to be larger than the single flight results presented in this study because the altitude shifts and routing approved by air traffic control will not be ideal.