The authors study the appearance of a sustainable city logistics, along with the issues it raises for the large retailers that have decided to develop an important network of stores in town. Unlike the large stores located in remote peripheral areas, the stores located in town face legal and operational constraints that complicate the supply. A case study carried out with a large French retailer (Gamma) is used to examine the implementation conditions of its sustainable strategy. This company is considered as one of the pioneers of a sustainable view of city logistics in France. The paper shows that the success of sustainable strategy is strongly dependent on both an upstream involvement of the company in the decision-making process introduced by the local authorities, and a regular scanning activity of best practices to integrate the most advanced technological innovations. The paper also underlines the importance of a narrow interaction between companies and local authorities to jointly improve the city logistics organisation. A company as a large retailer that wishes to develop its network of stores in town should not wait passively for new legal constraints to appear to start adapting to them. On the contrary, it should anticipate them and offer innovative solutions to the local authorities, which will create value for both parties.