The temporospatial distribution of proteins within cilia is regulated by intraflagellar transport (IFT), wherein molecular trains shuttle between the cell body and cilium. Defects in this process impair various signal-transduction pathways and cause ciliopathies. Although K63-linked ubiquitination appears to trigger protein export from cilia, the mechanisms coupling polyubiquitinated proteins to IFT remain unclear. Using quantitative proteomics, we identified that a complex of CFAP36, a conserved ciliary protein of previously unknown function, and ARL3, a small GTPase involved in ciliary import, binds polyubiquitinated proteins and links them to retrograde IFT trains. CFAP36 uses a coincidence detection mechanism to simultaneously bind two IFT subunits accessible only in retrograde trains. Depleting CFAP36 accumulates K63-linked ubiquitin in cilia and disrupts Hedgehog signaling, a pathway reliant on the retrieval of ubiquitinated receptors. These findings advance our understanding of ubiquitin-mediated protein transport and ciliary homeostasis, and demonstrate how structural changes in IFT trains achieve cargo selectivity.