In the books the Night’s King also began as a human, but it isn’t known if he ever actually became an Other.
He was the 13th lord commander of the Night’s Watch (note the unlucky number). The story goes that he saw a blue-eyed woman from the Wall (not so tall back then) and fell in love with her, becoming obsessed. The woman was either an Other herself or a wight, it isn’t known. He brought her over the Wall (note brought), married her and declared her his queen. When they had sex, he gave her “his soul,” and they eventually used sorcery to enslave the Night’s Watch. The Stark king, Brandon the Breaker, and the wildling king (Joramun, of Horn of Winter fame) joined forces to defeat him. In doing so they learned that he had been making human sacrifices to the Others. He was defeated and his name was wiped off the history books, so “Night’s King” is the only name he’s known by. No one knows exactly who he was, but the prevailing theory is that he was a Stark and that Brandon had to fight and kill his own uncle, brother, cousin, etc.
On the show he’s an as-yet-unidentified First Man whom the Children of the Forest made into the first Other. Seeing as the Night’s Watch was only ever formally created to fight the Others the first time around, it isn’t possible for this guy to be the first Other and the 13th lord commander of the Watch. So the show’s Night’s King and the books’ are different (and GRRM said as much ages ago, people just weren’t sure if he was being coy).