Globalization has created a mindset for SMEs to think outside the box in order to be above board in the ever-changing world trends in business. Despite the important role of SMEs in economic growth, SMEs participation in international business has been a far cry for our nation Nigeria in terms of export. This requires SMEs to establish robust market innovation capabilities as well as organizational innovation capabilities to keep them fit to compete gallantly. On this backdrop this study examined the effect of innovation on SMEs international business in Nigeria. The study also focused on export-oriented SMEs in Nigeria. Descriptive research design was used. A stratified sample size of 228 was drawn from the population of 529 performing exporters in Nigeria using a structured questionnaire formulated for the purpose of the study. Multiple regressions were used to analyze data and the existing relationship between selected variables. The findings of the study revealed that both Market and Organizational Innovation exerted significant positive effect on SMEs international business in Nigeria. The study therefore recommended that SME exporters in Nigeria exhibit market innovation skills and knowledge of product to increase market share across borders and generate more profit for the enterprises. SMEs were also recommended to come up with new organizational methods to improve their services to customers, and also imbibe change as a constant means for achieving business objectives such as profitability, growth and expansion.