The present work reports ultra-small polyelectrolyte-coated water insoluble Tb(III) complex species with bright Tb(III)-centered luminescence resulted from efficient ligand-to-metal energy transfer as efficient labels for Hep-2 cells. The flow cytometry data revealed the enhanced cellular uptake of negatively charged nanoparticles coated by the polystyrenesulfonate (PSS)-monolayer versus the positively charged nanoparticles. The latter are obtained by layer-by-layer deposition of polyethyleneimine (PEI) onto PSS-coated ones. Confocal and TEM images of Hep-2 cells exposed by the colloids confirm favorable cell internalization of the PSS- compared to PEI-PSS-coated colloids illustrating unusual charge-effect. Dynamic light scattering data indicate significant effect of the biological background exemplified by serum bovine albumin and phosphatidylcholine-based bilayers on the exterior charge and aggregation behavior of the colloids. The obtained results reveal the PSS-coated nanoparticles based on water insoluble Tb(III) complex as promising cell labels.