With unprecedented growth of urbanization, the issue of health and health seeking behavior (HSB) among the urban poor is spiralling. Taking prompt and appropriate health measures becomes unlikely to the urban poor due to the prevailing socioeconomic reality. Illuminating Healthcare seeking behaviour of the Poorest of the Poor (PoP), who are under healthcare safety net, in Gullele Sub City of Addis Ababa was the objective of this study. To meet the objective, a mixed approach was employed. A total of 168 PoP who are eligible for fee waiver were surveyed through multistage cluster sampling. In addition, eight PoPs and six key informants which were selected through purposive sampling were interviewed. To analyse the quantitative data, Statistical Package for Social Sciences (SPSS) version 20 was used. Beyond descriptive statistics that was used to summarize the data, further statistical tests such as t test, one way ANOVA, Pearson’s Correlation and Chi Square were employed to see differences and associations. 95 % confidence interval (CI) and 5% margin of error was considered during the statistical analysis. The qualitative data was analysed thematically and integrated with the quantitative one. Accordingly, self-care, spiritual healing, traditional healer and trained allopathic are the major treatment alternatives of the PoP. A statistically significant difference in prompt healthcare utilization was found among the categories of sex, religion, religiosity and income, but insignificant for others. Though the fee waiver scheme has resulted in progress in the HSB of the PoP, the paradox behind low prompt utilization of healthcare has to be researched for evidence based practice.