In an increasingly demanding environment, users complain because they are dissatisfied with the services rendered. This study investigates the complaining behaviour of public library users in a Malaysian state. A self-administered questionnaire was randomly distributed to 99 dissatisfied adult users of the Labuan Public Library, which is located in the Federal Territory of Labuan, Malaysia. The survey revealed that public library users, who perceive the service of the library to be free, are more likely to complain to a third party about their dissatisfaction. There are some users who complain directly to the personnel or person in charge of the department, or chief librarian at the time of dissatisfaction. Users’ complaints can be a powerful resource for the library management to use in making strategic and tactical decisions that could prevent them from switching services. In addition, discussion, conclusions and recommendation for future research are also presented.