Proteins larger than ~40 kDa are selectively transfered through the nuclear pore complexes by energy-dependent mechanism that requires additional transport factors, called karyopherins, which recognize nuclear localization signals (NLSs) in their cargo proteins. Recent studies recognized some important events in the nuclear envelope evolution, and the possible ancestors of key elements of import machinery – nuclear pore complexes and karyopherins, were supposed. However, the origin and evolution of NLSs is obscure. Methods. To address this question, we analyzed the data on the NLSs and their localization relative to protein domains, and also studied possible NLS-containing regions inside prokaryotic proteins. Results. The result of the current work indicate that (1) NLS could pre-exist in prokaryotic proteins inside domains that bind nucleic acids or proteins; (2) during the course of evolution, some NLSs could be integrated within functional domains and co-evolve with them; (3) the structure of some functional domains of non-nuclear proteins allows them to function as an NLS, which requires the development of mechanisms to prevent the import of these proteins into the nucleus. Conclusions. Our data indicate that enriched with positively charged amino acids regions of nucleotide-binding domains can serve as genuine NLSs. These NLSs are integrated into domains, and their evolution might be depended on the evolution of the domain. Funding. This work was supported by the Russian Science Foundation (grant 18-14-00195).