The study aims to examine relationships between customers’ satisfactions and service quality at Vietnam Telecom Services Company. Quantitative methods and SPSS software (version 20) were used and data were collected from 317 mobile telecommunications service users of Vietnam Telecom Services Company (VinaPhone) during May to June 2015 in Hanoi. Results showed service quality and overall customer satisfaction were strongly related at Vietnam Telecom Services Company in Hanoi. The findings will help Vinaphone to develop better strategies for improving their customers’ satisfaction.