Six species of terns, which breed on the Arabian Peninsula, were examined for head chewing lice of the genus Saemundssonia in four different islands around the coasts of Saudi Arabia, both in the Red Sea and in the Arabian Gulf. Four louse species were collected: Saemundssonia laticaudata, Saemundssonia melanocephalus, Saemundssonia meridiana and Saemundssonia sternae, of which three are recorded for the first time from this region. Also, we record three new host-louse associations for the world-Saemundssonia laticaudata and Saemundssonia sternae from white-cheeked terns and Saemundssonia melanocephalus from Saunders's terns-including a host-switch event of Saemundssonia laticaudata on white-cheeked terns in the Karan Island population. Gene bank data for the COI gene from seven species of Saemundssonia that infest marine birds were used to propose evolutionary trees using two different statistical methods: maximum parsimony (MP) and neighbour joining (NJ). The result indicated that the tree which was produced by NJ is likely to be more accurate as it appeared more compatible with hosts' phylogeny. The trees indicate relationships between tern Saemundssonia and congeneric species from other marine birds, especially from gulls. An ANOVA was also conducted to test the mean parasite load for each tern species studied, and results indicate that there is a relation between louse loads and colonization behaviour of the hosts. Data from lice examined and illustrations of lice and their hosts are also included.