Detection and quantification of bioanalytes using near infra-red (NIR) probes provide several advantages, viz, negligible scattering of light, minimum interference from the background matrices, deep sample penetration, etc. Herein, we report a supramolecular dye-polymer complex, comprising of mono-cationic LDS-798 dye and multi-anionic polystyrene sulfonate (PSS), as a promising NIR emitting turn-on probe for protamine (Pr) sensing. The supramolecular complex displays moderate fluorescence enhancement for LDS-798 due to its binding onto PSS surface. Strikingly, in the presence of Pr, this complex displays further enhancement in its emission intensity, which is also substantiated by a significant increase in the excited-state lifetime of LDS-798 dye. This turn-on response is found to be highly selective towards Pr, which is attributed to the structural change taking place for the anionic PSS on its interaction with highly cationic Pr molecule. Such a conformational change creates several cavities into the modified PSS structure, which can suitably encapsulate LDS-798 dye via strong hydrophobic interaction. Accordingly, there is large decrease in the radiationless decay processes for the excited dye molecules, making them strongly emissive in nature. Furthermore, LDS-798—PSS complex is found to be quite robust against changing temperature and ionic strength of the medium, indicating its possible use as a fluorescent probe over a wide range of temperature and salinity.