We present protein-PAINT-the implementation of the general principles of PAINT (Point Accumulation for Imaging in Nanoscale Topography) for live-cell protein labeling. Our method employs the specific binding of cell-permeable fluorogenic dyes to genetically encoded protein tags. We engineered three mutants of the bacterial lipocalin Blc that possess different affinities to a fluorogenic dye and exhibit a strong increase in fluorescence intensity upon binding. This allows for rapid labeling and washout of intracellular targets on a time scale from seconds to a few minutes. We demonstrate an order of magnitude higher photostability of the fluorescence signal in comparison with spectrally similar fluorescent proteins. Protein-PAINT ensures prolonged super-resolution fluorescence microscopy of living cells in both single molecule detection and stimulated emission depletion regimes.