In this paper, a compartmental model for the transmission of the co-infection of cholera and malaria was developed and analyzed. The reproduction numbers for each sub-model and the full model were calculated. In order to study the impact of each disease on the other, a sensitivity analysis was carried out and its results show that malaria infection is linked to an increased risk of cholera, whereas cholera infection is not associated with an increased risk of malaria. A set of seven variables’ controlling strategies, ranging from vector control to water sanitation and treatment, were added to the model; and their effect have been studied using the optimal control technique. Numerical simulations show the impact of these controlling strategies on the reduction of the new infections in humans and vectors as well as the reduction of the Cholera vibro concentration in the environment. In order to find the most cost-effective controlling strategy, and all the three major cost-effectiveness analysis techniques were implemented to our model after we categorized all the controlling strategies into three scenarios, namely Cholera controlling strategy, Malaria controlling strategy, and Cholera-Malaria controlling strategy. The numerical results show that the most cost-effective controlling strategy in reducing the number of new infection is the vector control strategy.