Police released sketches of the suspects but offered few other clues about the men or their possible whereabouts.
The warning of potential bombers on the loose in India's financial and entertainment center came weeks after the country's two key stock exchanges, both in Mumbai, received e-mailed bomb threats. The sender of the e-mails has not been identified.
Mumbai police have been on alert since the July 2006 commuter train bombings killed 188 people and wounded more than 800. Thirteen men allegedly linked to two Islamic militants groups, Pakistan-based Lashkar-e-Tayyaba, or Army of the Pure, and the Students' Islamic Movement of India, have been arrested over those blasts.
Police did not say if the suspects whose sketches were released Friday belonged to any known militant group, Muslim or otherwise.
Two of the suspects looked middle-aged, one with a mustache and one with a beard. The third person looked older and was clean shaven.
The sketches were based on information provided by a taxi driver who drove the three to Mumbai's popular Hindu Siddhi Vinayak temple, the Haji Ali and Mahim mosques, and two luxury hotels earlier this week, said K. L. Prasad, a senior police official.
The driver grew suspicious because the three were discussing in hushed tones the security at the places they visited, Prasad told reporters. When asked by the men to deliver a bag, the driver refused, fearing it might contain explosives. He then contacted police.
"By the taxi driver's description, the three seem to be fidayeen (suicide bombers) and we have given the description to the public to come forward with any information," Prasad said, adding that police had no other information about the suspects.
He said a woman had accompanied the three men in the taxi, which they had hired for two days, but did not explain why police had not yet released any description of her.
Mohammed Kadir, another taxi driver, said he would be extra careful while moving around Mumbai. "Blasts are happening everywhere. Police need to be more vigilant."
India has been hit by a wave bombings over the past two years, killing more than 300 people. The targets have included markets crowded with holiday shoppers, Hindu temples, a cinema and mosques.
Authorities have blamed Islamic militants for nearly all the attacks, saying they were meant to provoke violence between India's Hindu majority and Muslim minority. But officials have provided little concrete evidence linking specific groups to the attacks.
Mumbai, earlier known as Bombay, also was the target of bombings in 1993 that killed 257 people. The blasts are believed to have been acts of revenge for the demolition by Hindu extremists of a 16th century mosque in northern India.