Municipal solid waste management is one of the major challenges that cities in developing countries are facing. Although waste collection services are critical to build a smart city, the focus of both scholarship and action/activism has been more on the utilization of waste than on collection. We devised a choice experiment to elicit the preferences of municipal residents with regard to the various attributes of solid waste collection services in the Bharatpur Metropolitan City of Nepal. The study showed that households identify waste collection frequency, timing of door-to-door waste collection services, and cleanliness of the streets as the critical elements of municipal waste collection that affect their welfare and willingness to pay. While almost all households (95%) were participating in the waste collection service in the study area, more than half (53%) expressed dissatisfaction with the existing service. Women were the main actors engaged in waste collection and disposal at household level. The results of the choice analysis suggest that households prefer a designated waste collection time with waste collection bins placed at regular intervals on the streets for use by pedestrians who often throw garbage on the streets in the absence of bins. For these improvements, households were willing to pay an additional service fee of 10–28% on top of what they were already paying. The study also finds that municipal waste collection can be improved through the involvement of Tole Lane Committees in designing the timing and frequency of the service and by introducing a system of progressive tariffs based on the number of storeys per house.