Although the tourism industry in Albania has had an impressive growth in the last years, it is currently facing several challenges. This study examines the determinants of Albanian tourism small and medium-sized enterprise (SME) performance. More specifically, the direct effects of customer orientation (CO) on performance and its indirect effects mediated by innovativeness and innovation behavior are investigated. Quantitative data from a survey conducted on 211 Albanian tourism SMEs, together with qualitative information gathered from personal interviews, are considered. Results indicate that CO has a direct positive impact not only on performance but also on both innovativeness and innovation behavior. However, none of these two dimensions of innovation play a mediating role in the relationship between CO and performance. Implications from these findings are discussed.