This paper aims to design a methodological proposal to improve the innovation of companies belonging to the logistics sector in Cartagena, Colombia. The multiple case study methodology was applied, where nine axes that directly affect organizational innovation (strategy, culture, planning, people, tools, products/services, processes, efficiency, and capitalization) were analysed. The sample consisted of five Logistics Service Providers located in Cartagena. Among the main results of the research, it was found that planning is fundamental for improving organizational innovation because it is essential to have a stipulated strategic direction and to design a plan to propitiate an innovative culture in the company. Additionally, the company's diagnosis showed that most have innovative resources and processes; however, they do not have the necessary tools to implement the processes effectively. Finally, four of the five companies are working to develop an innovative culture, which places culture as the second most crucial axis after planning. These results led to the proposal of a methodology that seeks to improve organizational innovation levels and mainly focuses on three phases: Strategic Direction, Processes, and Results.