Kings of Men was apparently a title of the Númenóreans, given to them by the men of Middle-earth during the years of the Second Age.

When Sauron claimed this title because of his great dominions in Middle-earth during the Second Age, the pride of Ar-Pharazôn of Númenor was aroused. He sailed to Middle-earth, humbled Sauron, and secured the title himself.
Encyclopedia entry originally written by tarkena