This paper investigates how firm-level innovation and productivity affect the export propensity in manufacturing firms in seven Eastern European Union countries. With respect to innovation activities, we analyze the complementarity between pair-wise product, process and non-technological (organizational and marketing) innovations when the objective function is represented by the exporting probability of a firm. Analyzing CIS2008 data, we find that productivity always has a positive and significant impact on the exporting propensity of firms. Furthermore, complex innovative firms, when large in size and/or from medium high–high technology sectors, can take advantage in terms of a higher attitude to export than non-innovators and simple innovators. By considering these results, governments have to introduce policies that can induce firms, especially small and medium ones, to implement complex innovations. This is fundamental in order to be more productive and more competitive.