The Russian-made AN-32 was on its way to Port Blair, the capital of the Andaman and Nicobar chain of islands, from the southeast city of Chennai when it disappeared from radar.
There were six crew on the aircraft, a workhorse of the air force.
A navy spokesman said surveillance planes and ships were searching for the aircraft. It was carrying service personnel to the strategic islands near the Malacca Straits, where India has a military base.