Primary ciliary dyskinesia (PCD) is caused when defects of motile cilia lead to chronic airway infections, male infertility, and situs abnormalities. Multiple causative PCD mutations account for only 65% of cases, suggesting that many genes essential for cilia function remain to be discovered. By using zebrafish morpholino knockdown of PCD candidate genes as an in vivo screening platform, we identified c21orf59, ccdc65, and c15orf26 as critical for cilia motility. c21orf59 and c15orf26 knockdown in zebrafish and planaria blocked outer dynein arm assembly, and ccdc65 knockdown altered cilia beat pattern. Biochemical analysis in Chlamydomonas revealed that the C21orf59 ortholog FBB18 is a flagellar matrix protein that accumulates specifically when cilia motility is impaired. The Chlamydomonas ida6 mutant identifies CCDC65/FAP250 as an essential component of the nexin-dynein regulatory complex. Analysis of 295 individuals with PCD identified recessive truncating mutations of C21orf59 in four families and CCDC65 in two families. Similar to findings in zebrafish and planaria, mutations in C21orf59 caused loss of both outer and inner dynein arm components. Our results characterize two genes associated with PCD-causing mutations and elucidate two distinct mechanisms critical for motile cilia function: dynein arm assembly for C21orf59 and assembly of the nexin-dynein regulatory complex for CCDC65.