The Australian Maritime Safety Authority said on Thursday that the ship issued a distress call mid-afternoon and capsized 120 nautical miles north (200km) of the Indian Ocean territory, some 2,600km from the Australian mainland.
But Australian police said that early reports suggested up to 75 asylum seekers had died after the boat capsized en route from Sri Lanka.
"There is a capsized vessel 120 nautical miles north of Christmas Island, there's believed to be approximately 200 people on board," an AMSA spokeswoman told AFP.
"We can confirm there are survivors but we can't confirm numbers at this stage," she said. "The Indonesian search and rescue authorities are co-ordinating the response."
Al Jazeera's Andrew Thomas, reporting from Sydney on Thursday, said: "Details at this point are still sketchy".
"This boat was probably headed to Christmas island and it is understood that up to 200 people were on the boat," he said.
Australian Customs said a border patrol aircraft spotted the vessel in distress in Indonesia's search and rescue zone at about 0500 MT and "it is believed up to 200 people could be on board".
Three merchant vessels and two Australian military ships had responded to a regional maritime alert and were on their way, and a fixed-wing P3 Orion aircraft was on the scene, according to AMSA.
Two aircraft had been deployed including one equipped with life rafts, Customs added.
A number of asylum boats have been intercepted in the area in the past 24 hours carrying more than 100 passengers, prompting Home Affairs Minister Jason Clare to issue a statement calling for an urgent political compromise.
"Let's remember what this is all about - 200 people died off the coast of Indonesia and another 11 died off the coast of Malaysia," Clare said in a statement earlier on Thursday, referring to previous recent accidents.
Series of accidents
So far this year 62 vessels carrying 4,484 boatpeople have been intercepted off Australia, an unprecedented number in a six-month period.
Arrivals have increased steadily since Canberra was forced to abandon a so-called "people swap" deal with Malaysia by the High Court last year and roll back its mandatory detention policy for boatpeople.
The government has had to release hundreds of asylum-seekers into the community while their applications are processed due to the strain on detention centres, the budget for which has now spiralled above $1 billion.
Though they come in relatively small numbers by global standards asylum-seekers are a sensitive political issue in Australia, dominating 2010 elections due to a record 6,555 arrivals.
Indonesia is a common transit point for those trying to reach Australia's Christmas Island, which is closer to Java than mainland Australia, but many of the overloaded, rickety vessels do not reach their destination.
In December, a boat carrying around 250 mostly Afghan and Iranian asylum-seekers sank in Indonesian waters on its way to Christmas Island, with only 47 surviving.
Some 50 refugees were killed in a horror shipwreck on the remote island's cliffs back in December 2010 when their leaky wooden vessel was dashed on the rocks.
Fifteen were children aged 10 years or younger, with one a baby just three months old.