Ethiopian and Eritrean asylum seekers demonstrated outside canton Vaud's parliament on Tuesday for their residency to be legitimised.
They cannot be expelled since their home countries will not take in people who have been forcibly repatriated.
The demonstrators waved posters in front of the parliament building in Lausanne saying "We've worked in Switzerland for years" and "Our children were born in Switzerland".
At a media conference, representatives of the group - which numbers 175 - said they were "bitterly disappointed" and "angry".
They said they had integrated into Swiss life and had paid taxes and social-insurance contributions.
Many of the female demonstrators with children held up their family records provided by the canton.
One month ago the Swiss government decided to withdraw the protestors' work permits, which are due to expire at the end of July.
Ethiopia and Eritrea will only let people return if they do so voluntarily.
The authorities in canton Vaud now want to speed up the process of voluntary return.