Optimization in logistics subsystems is becoming one of the fundamental goals, and parcel lockers, as an innovative solution, can positively impact all logistics processes. This paper focuses particularly on the concept of parcel lockers as an efficient and sustainable solution for cities, provided that they are properly implemented in accordance with users’ needs and the urban structure. The aim of this paper is to determine the suitable locations for implementation of parcel lockers in the area of the Tuzla distribution center, in order to contribute to sustainable urban logistics. Locating parcel lockers in unsuitable locations can lead to insufficient usage and increased costs, which further justifies the need for this research. In order to determine the optimal locations for installing the parcel lockers of the X-Express company within the Tuzla distribution center area, multi-criteria decision-making (MCDM) methods were applied. The IMF SWARA (Improved Fuzzy Step-Wise Weight Assessment Ratio Analysis) method was used to determine the weights of criteria, while the ARAS (Additive Ratio Assessment) method was applied to rank potential locations. Sixteen locations were evaluated based on eight criteria, and the model showed that the most favorable locations are A6, A5, and A3. The least favorable location is A2. This methodological approach allows for an objective selection of the most suitable locations that will contribute to more efficient delivery, cost reduction, and improved user experience. Through the integration of innovative technologies and strategic planning, the paper offers solutions that can significantly improve urban logistics and system sustainability. Sensitivity and comparative analyses presented in the paper demonstrate the stability of the initially obtained results, as well as all possible changes.