Tourism is one of the most important sectors of the Cypriot economy and a key pillar of the country’s economic development. Particular the hotel industry creates labor demand that exceeds labor supply where the number of local staff is not sufficient to meet the market needs. Moreover, the phenomenon of the hotel labor market is that the high worker shortage coexists with high unemployment impacting negatively the quality of services offered to customers. Under these circumstances, the hospitality industry's biggest call is to attract, recruit, and retain skilled employees. To fill the bottlenecks, hoteliers resort to labor pools from abroad, mainly EU citizens from Greece and Eastern European countries. This paper represents the results of the industry-based research focusing on the Greek and Slovakian hotel labor market, including but not limited to: (i) elements that impede staff mobility to Cyprus; and (ii) employer and job market characteristics that the ongoing human capital seeks to find in another country in order to engage in professional mobility. The aim of the research is to understand the features (skills and needs) of the potential employees from those pools which affect the willingness and easy to work in Cyprus. The results have been achieved by receiving information from the supply side that is from the potential candidates who are interested in working in Cyprus hotels, coming from Greece and Slovakia (the second as a typical Eastern European country).