Malaria, caused by the apicomplexan parasite Plasmodium, threatens 40% of the world's population. Transmission between vertebrate and insect hosts depends on the sexual stages of the life-cycle. The male gamete of Plasmodium parasite is the only developmental stage that possesses a flagellum. Very little is known about the identity or function of proteins in the parasite's flagellar biology. Here, we characterise a Plasmodium PF16 homologue using reverse genetics in the mouse malaria parasite Plasmodium berghei. PF16 is a conserved Armadillo-repeat protein that regulates flagellar structure and motility in organisms as diverse as green algae and mice. We show that P. berghei PF16 is expressed in the male gamete flagellum, where it plays a crucial role maintaining the correct microtubule structure in the central apparatus of the axoneme as studied by electron microscopy. Disruption of the PF16 gene results in abnormal flagellar movement and reduced fertility, but does not lead to complete sterility, unlike pf16 mutations in other organisms. Using homology modelling, bioinformatics analysis and complementation studies in Chlamydomonas, we show that some regions of the PF16 protein are highly conserved across all eukaryotes, whereas other regions may have species-specific functions. PF16 is the first ARM-repeat protein characterised in the malaria parasite genus Plasmodium and this study opens up a novel model for analysis of Plasmodium flagellar biology that may provide unique insights into an ancient organelle and suggest novel intervention strategies to control the malaria parasite.