This paper provides an empirical analysis about the relationship among innovation, productivity and exporting propensity within manufacturing firms of seven Eastern European Union countries. We analyse marginal effects of product, process and organisational-marketing innovations and test complementarity among them when the objective function is represented by the exporting propensity of a firm. Analysing CIS2008 data, we obtain that productivity improves exporting propensity; the more firms innovate the higher is their exporting probability; complementarity between process and organisational-marketing innovations is accepted in medium high and high technology firms. Complementary innovation strategies are detected for Bulgarian firms, even if Bulgaria is one of the least innovative Eastern European countries.