Objectives: In this study we investigated an outbreak of Vibrio cholera O1 Ogawa serotype, occurred during December 2014 in Kudat district, situated in Sabah state of the Malaysian part of Borneo. Methods: Active case detection and contact tracing were done at respective localities by house to house survey. Passive case detection was done among acute gastroenteritis patients attended at various health facilities. To determine the source, samples from food, water and environment were taken. A case control study was also done to determine the risk factors. Results: A total of 44 symptomatic and 34 asymptomatic cases from 19 localities were investigated. 39 cases were detected through passive case detection. Median age of cases was 23 years. All cases belonged to serogroup O1 and Ogawa serotype. The epidemiological investigation of time, place, and person identified that V. cholerae cross-transmission might have occurred in two fish markets and the fish-loading port. Circumstantial evidences indicated that cholera was possibly transmitted through contaminated sea foods. Conclusions: We concluded that the life-style of Sea Gypsies is a challenge in cholera control; therefore vaccination might be an effective way to mitigate cholera in an outbreak prone area like Kudat. Keywords: Cholera, Kudat, Sabah, Malaysia, Sea Gypsy, Outbreak, Fish