Of course, because they are EU citizens. All EU citizens can travel freely. But immigrants need a visa since Cyprus is not in Schengen. This is the case with all non-Schengen EU countries, like, immigrants living in London need a visa to go to Paris, but a Romanian doesn't need visa to go to London. An immigrant in a Schengen country can travel to any other Schengen country plus new non-Schengen entrants: Cyprus, Romania, Bulgaria and Croatia. For example, i am an immigrant in Lithuania (Schengen) and i travelled to Cyprus and Romania with no visa (i can't even technically apply for one), plus many Schengen states.