Malaysian airlines offers best connections if you wish to travel on a holiday together to Kuala Lumpur, Malaysia and Bali, Indonesia. Malaysian airlines flies from many cities in India like Delhi, Mumbai, Chennai, Hyderabad, Bangalore etc. Air Asia also has flight from many cities in India. Even if you are planning to travel from cities like Lucknow, Ahmedabad, Kolkata, Guwahati etc you will easily find good connection to fly to Kuala Lumpur, Malaysia and Bali. To book cheapest fare or early bird offers you must book in advance.