This paper dexamines the history of sexually transmitted diseases in Southeast Asia and explores the origins of venereal disease, specifically syphilis and gonorrhoea, in the region. The arrival of new diseases that accompanied Europeans from about 1500, is a subject that scholars have largely ignored in favour of the 19th and 20th centuries. While concentrating on the Indonesian archipelago, the paper also considers to other parts of Southeast Asia to investigate the impact of syphilis and gonorrhoea on the rate of population growth in the region. Unlike gonorrhoea, which was present before the arrival of Europeans, syphilis was a new disease whose introduction by the Portuguese had lethal consequences. Possibly, the propagation of Islam and Christianity in island Southeast Asia after 1500 and of Buddhism in mainland Southeast Asia, were important mitigating factors in checking the spread of syphilis.