A search map provided in the Australian government's "Definition of Underwater Search Areas" report. Australian Transport Safety Bureau

SYDNEY—The hunt for Malaysia Airlines Flight 370 entered a new phase on Thursday as authorities moved the search area for the third time in as many months, focusing on an area of the southern Indian Ocean buffeted by fierce winds and storms.

Authorities conceded the decision to move to an area as much as 600 miles south from where ships and planes have been deployed since early April is based on educated guesswork, given the limited data about the final movements of Flight 370 after it went missing on March 8 with 239 people on board.

A wall of hope for missing Malaysia Airline Flight 370 at Kuala Lumpur International Airport. European Pressphoto Agency

The shift comes as private contractors ready plans to take over what would be the largest undersea search mission in history, with a deadline for bids on Monday. Authorities are offering as much as 60 million Australian dollars (US$56 million) for a company or research organization to carry out a search over 20,000 square miles of remote ocean using sonar equipment that may take as long as 300 days to complete.

The Australian Transport Safety Bureau aims to spend about four weeks reviewing the bids before selecting a contractor to lead the rebooted search. That contractor will then have only a month to mobilize crew, equipment and ships from around the world to the new search area ahead of a restart in August.

Scientists and aviation experts spent weeks analyzing signals sent from Flight 370 to a telecommunications satellite owned by Inmarsat PLC before concluding the plane likely flew faster than previously thought and turned south out of the Malacca Strait. These experts now think the plane covered a greater distance across the Indian Ocean.

"The only data we have now is the Inmarsat data," said Charitha Pattiaratchi, head oceanographer at the University of Western Australia in Perth. "There is no physical data, and that's the issue–you're in the dark."

Experts remain confident that the plane crashed within a few miles of a final ping transmission sent to an Inmarsat satellite on the morning of March 8, which they believe represents the moment the plane ran out of fuel. But the plane could have been anywhere along an arc extending thousands of miles of sea when it went down.

Warren Truss, Australia's deputy prime minister, said it was "highly, highly likely" that Flight 370 was on autopilot when it traveled across the Indian Ocean because of the orderly path it is believed to have taken until it ran out of fuel.

Passenger Profiles

Past searches costing tens of millions of dollars have focused on areas along the arc around 700 miles apart, from desolate patches of sea near the French Antarctic territory of Kerguelen, to an area of offshore coral reefs near Exmouth, which is exposed to tropical cyclones. None of these operations, which involved military aircraft and ships from nations including the U.S. and China, found any debris related to the missing plane.

For searchers preparing to renew the hunt for the missing plane, the new area has some advantages. It shifts away from an area that included extremely deep seas such as the Wallaby-Zenith Fracture Zone, a tectonic rip in the Earth's surface agitated by movements between the Australian and Greater Indian continental plates that descends down to 4.9 miles at its lowest point.

That area would only have been accessible to one device–the Chinese-owned Jiaolong minisub–after another underwater vehicle known as the Nereus imploded off the coast of New Zealand in May, said David Gallo, director of special projects at the Woods Hole Oceanographic Institution.

The new search area runs from the South East Indian Ridge in the south – a narrow area of sea that has been mapped by U.S. researchers in the 1990s – through a deep abyssal plain to just west of the Broken Ridge, which is as shallow as 3,250 feet in places.

However, this new area also presents several challenges. It covers a desolate patch of sea close to the "Roaring 40s," an area lashed year round by fierce winds and storms. Previous air-and-sea search efforts in the remote southern Indian Ocean through late March had to be called off a number of times when waves and gale-force winds became too dangerous, requiring even the 516 foot navy vessel HMAS Success to evacuate the search area.

Two ships have been conducting bathymetric surveys of the sea floor as a precursor to a more detailed undersea search. These maps of the seabed are important because they will help expensive underwater sonar equipment navigate possible ocean trenches and ridges, limiting the chances that they could be damaged or lost.

The Chinese ship Zhu Kezhen has most recently been active in the southern part of the old search area, near where the Haixun 01 picked up acoustic signals with hand-held hydrophones in early April, a person close to the investigation said. Dutch oil and gas company Fugro NV's bathymetric vessel the Equator was deployed to help speed up the bathymetric survey in mid-June, and sent to an area further south that is in an area indicative of the new search zone, a person close to the investigation said.

It isn't clear how much of this bathymetric work overlapped with the refined search area unveiled Thursday.

Searchers in planes and aboard ships initially focused of an area of the Indian Ocean far to the west of Perth from mid-March, based on preliminary calculations and reinforced by a number of satellite sightings of possible debris. However, objects pulled from the ocean turned out to be floating garbage such as discarded fishing equipment.

Authorities then shifted the search area some 700 miles northeast in late March based on radar analysis. A series of electronic signals detected underwater using a pinger locator towed behind the Australian naval vessel Ocean Shield raised hopes of a breakthrough. However, an underwater search using the Bluefin-21 drone failed to find any trace of the missing plane.

Write to Daniel Stacey at daniel.stacey@wsj.com