Many developed countries, like Australia, maintain a high population level immunity against measles, however, there remains a risk of acquisition of measles in non-immune travellers and subsequent importation into Australia leading to localised outbreaks. In this study, we estimate the incidence of measles and describe characteristics including immunisation and pre-travel health seeking behaviour of notified cases of measles in New South Wales and Victoria, Australia between February 2013 and January 2014. Cases were followed up by telephone interview using a questionnaire to collect information of demographic and travel characteristics. In NSW, the incidence was highest in age group 0–9 years (20/million population) whereas in Victoria the highest incidence was observed in 10–19 (23/million population) years group. Out of 44 cases interviewed, 25 (56.8%) had history of travel outside of Australia during or immediately prior to the onset of measles. Holiday (60%) was the main reason for travel with 44% (11/25) reporting visiting friends and relatives (VFR) during the trip. The major reason described for not seeking prior medical advice before travel were “no perceived risk of diseases” (41%) and “previous overseas travel without any problem” (41%). Of the 25 measles cases with recent overseas travel during the incubation period, one reported a measles vaccine prior to their recent trip. Four cases were children of parents who refused vaccination. Twenty out of 25 (80.0%) had attended mass gathering events. Young adults and VFR travellers should be a high priority for preventive strategies in order to maintain measles elimination status.