In addition to their role in motility, eukaryotic cilia serve as a distinct compartment for signal transduction and regulatory sequestration of biomolecules. Recent genetic and biochemical studies have revealed an extraordinary diversity of protein complexes involved in the biogenesis of cilia during each cell cycle. Mutations in components of these complexes are at the heart of human ciliopathies such as Nephronophthisis (NPHP), Meckel-Gruber syndrome (MKS), Bardet-Biedl syndrome (BBS) and Joubert syndrome (JBTS). Despite intense studies, proteins in some of these complexes, such as the NPHP1-4-8 and the MKS, remain poorly understood. Using a combination of computational analyses we studied these complexes to identify novel domains in them which might throw new light on their functions and evolutionary origins. First, we identified both catalytically active and inactive versions of transglutaminase-like (TGL) peptidase domains in key ciliary/centrosomal proteins CC2D2A/MKS6, CC2D2B, CEP76 and CCDC135. These ciliary TGL domains appear to have originated from prokaryotic TGL domains that act as peptidases, either in a prokaryotic protein degradation system with the MoxR AAA+ ATPase, the precursor of eukaryotic dyneins and midasins, or in a peptide-ligase system with an ATP-grasp enzyme comparable to tubulin-modifying TTL proteins. We suggest that active ciliary TGL proteins are part of a cilia-specific peptidase system that might remove tubulin modifications or cleave cilia- localized proteins, while the inactive versions are likely to bind peptides and mediate key interactions during ciliogenesis. Second, we observe a vast radiation of C2 domains, which are key membrane-localization modules, in multiple ciliary proteins, including those from the NPHP1-4-8 and the MKS complexes, such as CC2D2A/MKS6, RPGRIP1, RPGRIP1L, NPHP1, NPHP4, C2CD3, AHI1/Jouberin and CEP76, most of which can be traced back to the last common eukaryotic ancestor. Identification of these TGL and C2 domains aid in the proper reconstruction of the Y-shaped linkers, which are key structures in the transitional zone of cilia, by allowing precise prediction of the multiple membrane-contacting and protein-protein interaction sites in these structures. These findings help decipher key events in the evolutionary separation of the ciliary and nuclear compartments in course of the emergence of the eukaryotic cell.