City logistics operations are significantly affected by the rapid expansion of electronic commerce (e-commerce). The pressure of the demand is being transferred to the last-mile distribution, disproportionately increasing the workload of service providers, while affecting the overall cost and fulfillment times for the entire supply chain. In this study, the expectations and demands of consumers and online retailers concerning city logistics provision are captured. A questionnaire survey carried out, addressing independently the two target groups focusing on the market routines in Thessaloniki, Greece. The purpose is to record and analyze the market needs to identify niche areas that are under-served, and their service will maximize sustainability and the overall benefit for the local users and the society. In general, it was recorded that delivery speed, reliability and flexibility are essential for both user categories. Service providers should focus on under-served market segments to gain competitive advantages and benefit the overall city logistics system. Specific suggestions for researchers and practitioners are also provided.