Solvent exposed lysine residues are abundantly present in many proteins. Their highly reactive ε-amino groups serve as universal targets for coupling with active esters of various extrinsic labels including a vast arsenal of fluorescent probes. Here, we describe fluorescent properties and preferential localization of two frequently used fluorescent labels, AlexaFluor488 (AF488) and Cy3, on the surface of a small highly soluble serum protein neutrophil gelatinase-associated lipocalin (NGAL), which serves as a diagnostic marker for acute kidney failure. Using a standard protocol for labeling with either AF488-SDP or AF488-NHS, we achieved >95% labeling efficiency of the protein as determined by UV-vis absorption and electrospray ionization (ESI)-MS. However, fluorescence intensity of the labeled protein was less than 10% of the expected value. To understand the unusually high quenching of the probe, we identified the sites of AF488 attachments by means of LC-MS/MS combined with trypsin digestion. Surprisingly, we found that the AF488 label is not randomly distributed among accessible lysines but predominantly bound to the residues K125, K126, or K135, which are located in the NGAL calyx and are likely quenched by neighboring tryptophans and tyrosines. In contrast, when NGAL was labeled with Cy3, the probe's fluorescence was almost fully retained. The LC-MS/MS data indicated that Cy3 was predominately bound to another lysine, K31, on the protein surface on the opposite side of the calyx. Our findings suggest that a combination of the inherent properties of the label and the specifics of the protein microenvironment may selectively lead probes to specific lysine residues and thus challenge the common view that protein labeling is a random process.