Migration is an energetically expensive strategy to avoid adverse conditions and locate resource peaks. Many migrants follow predictable routes of known distance, allowing reliance on large energy reserves to fuel migration, with occasional refueling at consistent stop-over sites. Predictability of route, distance, and resources favor this strategy. Nomadic migrants that search for unpredictable resources cannot know the distance or route they must traverse. How do such migrants fuel these nomadic movements? Here we propose two strategies for solving this problem: Scouting Trip and Wandering Search strategies. For Scouting Trips, the animal deposits fat and then goes on an exploratory Scouting Trip, the maximum length of which is limited by the fat stores. If no rich patch suitable for settlement is discovered, the animal turns back while it still has sufficient reserves to get to the original starting point, where it refuels for another Scouting Trip. A variant of this strategy is to stop at a new refueling point discovered somewhere along the way on the Scouting Trip, and to use that as a new point of origin for the next Scouting Trip. The Wandering Search strategy, in contrast, is an open-ended exploratory trip fueled primarily by feeding en route. Fat reserves can be much smaller than for Scouting Trips, and stops to refuel would be frequent. This strategy requires that sufficient food for refueling be present essentially all along the travel route. We discuss factors that favor each of these strategies, and present evidence that one nomadic migrant, the red crossbill, employs primarily Wandering Search.