Centrioles are microtubule-based structures that play important roles notably in cell division and cilium biogenesis. CEP135/Bld10p family members are evolutionarily conserved microtubule-binding proteins important for centriole formation. Here, we analyzed in detail the microtubule-binding activity of human CEP135 (HsCEP135). X-ray crystallography and small-angle X-ray scattering in combination with molecular modeling revealed that the 158 N-terminal residues of HsCEP135 (HsCEP135-N) form a parallel two-stranded coiled-coil structure. Biochemical, cryo-electron, and fluorescence microscopy analyses revealed that in vitro HsCEP135-N interacts with tubulin, protofilaments, and microtubules and induces the formation of microtubule bundles. We further identified a 13 amino acid segment spanning residues 96–108, which represents a major microtubule-binding site in HsCEP135-N. Within this segment, we identified a cluster of three lysine residues that contribute to the microtubule bundling activity of HsCEP135-N. Our results provide the first structural information on CEP135/Bld10p proteins and offer insights into their microtubule-binding mechanism.