- Abstract Background Approximately 150,000 undocumented migrants (UM) who are medically uninsured reside in Israel, including ~50,000 originating from the horn of Africa (MHA). Free medical-care is provided by two walk-in clinics in Tel-Aviv. This study aims to compare the medical complaints of UM from different origins, define their community health needs and assess gaps between medical needs and available services. Methods This cross-sectional study included a random sample of 610 UM aged 18–64 years, who were treated in these community clinics between 2008 and 2011. The study compared UM who had complex medical conditions which necessitated referral to more equipped medical settings with UM having mild/simple medical conditions, who were treated at the clinics. Results MHA were younger, unemployed and more commonly males compared with UM originating from other countries. MHA also had longer referral-delays and visited the clinics less frequently. UM with complex medical conditions were more commonly females, had chronic diseases and demonstrated longer referral-delays than those who had mild/simple medical conditions. The latter more commonly presented with complained of respiratory, muscular and skeletal discomfort. In multivariate analysis, the variables which predicted complex medical conditions included female gender, chronic illnes and self-referral to the clinics. Conclusions The ambulatory clinics were capable of responding to mild/simple medical conditions. Yet, the health needs of women and migrants suffering from complex medical conditions and chronic diseases necessitated referrals to secondary/tertiary medical settings, while jeopardizing the continuity of care. The health gaps can be addressed by a more holistic social approach, which includes integration of UM in universal health insurance.