Cilia are small antenna-like cellular protrusions critical for many developmental signaling pathways. The ciliary protein Arl3 has been shown to act as a specific release factor for myristoylated and farnesylated ciliary cargo molecules by binding to the effectors Unc119 and PDE6δ. Here we describe a newly identified Arl3 binding partner, CCDC104/CFAP36. Biochemical and structural analyses reveal that the protein contains a BART-like domain and is called BARTL1. It recognizes an LLxILxxL motif at the N-terminal amphipathic helix of Arl3, which is crucial for the interaction with the BART-like domain but also for the ciliary localization of Arl3 itself. These results seem to suggest a ciliary role of BARTL1, and possibly link it to the Arl3 transport network. We thus speculate on a regulatory mechanism whereby BARTL1 aids the presentation of active Arl3 to its GTPase-activating protein RP2 or hinders Arl3 membrane binding in the area of the transition zone.