In this paper, we advance and test the idea that innovation and export are complementary strategies for SMEs' growth. We argue that innovation and export positively reinforce each other in a dynamic virtuous circle, and we identify and describe the process through which this complementarity relationship takes place. Participating in export markets can promote firms' learning, and thus enhance innovation performance. At the same time, through innovation, firms can enter new geographical markets with novel and better products, therefore making exports more successful, and, by the same token, they can also improve the quality - and consequently increase the sales - of the products sold domestically. We test our theory using an unbalanced panel of Spanish manufacturing firms over the period 1990-1999. We find robust empirical support for our hypothesis: consistent with the presence of complementarity, we show that the positive effect of innovation activity on firms' growth rate is higher for firms that also engage in exports, and vice versa. Furthermore, we show that, Ceteris paribus, firms' adoption of one growth strategy (e.g., entering export markets) positively influences the adoption of the other (e.g., innovation).