Conjugation of ubiquitin to an internal lysine is the initial step in the degradation of the majority of the substrates of the ubiquitin system. For several substrates, it has been shown that the first ubiquitin moiety is conjugated to the N-terminal residue. In all these substrates, however, the internal lysines also played a role in modulating their stability. To better understand the physiological significance of this novel mode of modification, it was important to identify proteins in which degradation is completely dependent on N-terminal ubiquitination. Also, although the experimental evidence for N-terminal ubiquitination is rather strong, nevertheless, it has remained indirect. Here we demonstrate that an important group of proteins that are targeted via N-terminal ubiquitination are the naturally occurring lysine-less proteins such as the human papillomavirus (HPV)-58 E7 oncoprotein and the cell cycle inhibitor and tumor suppressor p16(INK4a). For these proteins, the only residue that can be targeted is the N-terminal residue. Interestingly, p16(INK4a) is degraded in a cell density-dependent manner. Importantly, we provide for the first time direct evidence for N-terminal ubiquitination. Analysis of tryptic digest of the ubiquitin conjugate of HPV-58 E7 revealed a fusion peptide that is composed of the C-terminal domain of ubiquitin and the N-terminal domain of E7. With the abundance of native lysine-less proteins, among which are important viral and cell regulators, this novel mode of protein targeting has implications for both physiological and pathophysiological processes.