This paper investigates the service quality of travel agencies in the Republic of Macedonia from a customer perspective. Its authors applied a modified version of the SERVQUAL instrument for measuring service quality. The results of the performed paired sample t-testing indicated significant differences between expectations and perceptions, with two exceptions. A positive correlation was identified between expectation means and perception means as well as between perception means and gap score means, with a negative correlation identified between expectation means and gap means. Furthermore, factor analysis of the gap score means was performed, revealing the existence of 3 dimensions: customer orientation, reliability and tangibles. Data analysis showed negative gaps between expectations and perception on all three dimensions. Finally, by using the ANOVA test, significant differences among the gap scores of the three different classes of travel agencies (with “A”, “B” and “C” licenses) were determined, both in total and with regard to the identified dimensions. There are a number of areas of the travel agencies’ service quality where enhancements are needed in order to satisfy the customers more fully.