Nanoencapsulation is a promising method to improve the bioavailability of tea polyphenol (TPP). In this work, we adopted a green process to develop a new kind of complex coacervation core micelles (C3Ms) based on biopolymers for efficient tea polyphenol delivery. First, gelatin-dextran conjugate was synthesized using Maillard reaction. Then the C3Ms were produced by mixing gelatin-dextran conjugate with TPP. Variable factors on the self-assembly of the C3Ms were investigated. Under optimal conditions, the obtained C3Ms are of nanosize (average 86 nm in diameter) with narrow distribution. The formation of the C3Ms is attributed to hydrophobic interaction and hydrogen bonding instead of electrostatic interaction. Transmission electron microscope (TEM) and scanning electron microscope (SEM) results showed that C3Ms have a spherical shape with core-shell structure. ζ-Potential measurement suggested that the core is composed of gelatin with TPP, whereas the shell is composed of dextran segments. The encapsulation efficiency of the C3Ms is pH-independent, but the loading capacity is controllable and as high as 360 wt % (weight/weight of protein). In addition, the C3Ms show sustained release of TPP in vitro. MTT assay revealed that the C3Ms have comparable or even stronger cytotoxicity against MCF-7 cells than free TPP.