"Every ten minutes a new stateless person is born," UN refugee chief Antonio Guterres told reporters in Geneva, describing the situation as "absolutely unacceptable" and "an anomaly in the 21st century."
With its "I Belong" campaign, UNHCR aims to highlight the "devastating life-long consequences of statelessness" and push countries to rectify their laws to ensure no person is denied a nationality.
"Often they are excluded from cradle to grave, being denied a legal identity when they are born, access to education, health care, marriage and job opportunities during their lifetime and even the dignity of an official burial and a death certificate when they die," the agency said in its report.
"Statelessness makes people feel like their very existence is a crime," Guterres said.
People can become stateless due to a range of reasons, like discrimination based on ethnicity, religion or gender, or when a nation state falls apart.
War and conflict also often make it difficult to register births.
The report does not count the case of the Palestinians, since the UN General Assembly had recognised the State of Palestine, Guterres said.
The problem for many of the 4.5 million of Palestinians in the West Bank and Gaza and the millions more living as refugees around the world is that the State of Palestine has yet to approve its nationality laws, he said, insisting that this "very specific situation" required a "political solution".
The largest number of stateless people are to be found in Myanmar, which denies citizenship to some one million Rohingya Muslims, according to Guterres.
Myanmar considers the Rohingya illegal migrants from Bangladesh, which in turn considers the ones who cross the border illegal migrants from Myanmar.
In both countries, the group viewed by the UN as one of the world's most persecuted peoples faces widespread restrictions, including curbs on movement, education and marriage.
When nation states break apart, people are often also left in limbo, with more than 600,000 people for instance still left stateless after the disintegration of the Soviet Union more than 20 years ago.
In situations of war, conflict and turmoil, it also often becomes difficult to register births, especially among refugees, leaving them stateless.
A full 70 percent of babies born to Syrian refugees in neighbouring Lebanon and Jordan have for instance not received legal birth certificates, Guterres said.
A number of countries, including Iran and Qatar, also deny women the right to pass their nationality on to their children on an equal basis with men, "a situation that can create chains of statelessness that span generations," UNHCR warned.
'Statelessness is inhuman'
The world's perhaps most famous stateless person was Albert Einstein, who remained stateless from 1896, when he renounced his German citizenship, until 1901, when he became Swiss.
In an open letter, Guterres, UNHCR special envoy and Hollywood star Angelina Jolie, UN rights chief Zeid Ra'ad Al Hussein, Nobel Peace Prize laureates Shirin Ebadi and Desmond Tutu and others described what living without a nationality can mean.
"Statelessness can mean a life without education, without medical care or legal employment," the letter said, adding: "Statelessness is inhuman. We believe it is time to end this injustice."
The campaign aims to gather ten million signatures with the petition in its bid to eradicated statelessness within the next ten years.
The good news, UNHCR said, was that much progress had already been made towards resolving the issue, with more than four million stateless people gaining a nationality in the past decade due to legislative and policy changes.
A court ruling in Bangladesh in 2008 had for instance allowed 300,000 stateless Urdu-speakers to become citizens.
"Unlike many armed conflicts, it is wholly within the power of every concerned government to resolve statelessness," Guterres said.