Objective: Despite the political commitment of national governments and collaborative efforts by the World Health Organization (WHO) toward the actualization of intercultural healthcare system over the past decades, sub-Saharan African countries feature medical cohabitation rather than a truly integrated medical system. This hospital-based cross-sectional study analyzed the capabilities of nurses for complementary and traditional medicine (CTM) integration in Africa. Method: Practicing nurses (n = 210) were recruited to respond to the CTM Health Belief Questionnaire (CHBQ) in December 2016. Normality of data was evaluated using Kolmogorov–Smirnov statistic with a Lilliefors significance correction. The authors assessed the relationship among nurses' knowledge, personal use, and clinical practice of CTM, using Spearman's Rank Order Correlation (rho). The differences and associations in continuous and categorical baseline variables were determined with Mann–Whitney U test/Kruskal–Wallis H test and Pearson's Chi-square test, respectively, at p < 0.05 as statistically significant. Results: The overall mean score of nurses' knowledge of CTM therapies was 38 (interquartile range [IQR] 16). This low CTM-related knowledge reflected in the poor mean performance score of 30 (IQR 17) and 22 (IQR 6) for personal use and clinical practice of CTM, respectively, among nurses. Nurses, therefore, lacked the confidence to recommend CTM therapies to patients. Yet, nurses exhibited a high positive attitude to CTM (72.7 ± 12.5). In addition to significant associations among CTM-related knowledge, education (p = 0.023), and religion (p < 0.001), the study found a positive and statistically significant correlation among CTM-related knowledge, personal use (r = 0.556, p < 0.001), and professional practice of CTM (r = 0.349, p < 0.001). Conclusion: Given their substantial role in the primary and public healthcare system, improving nurses' knowledge of CTM through evidence-based nursing education and training remains the surest way to achieve appropriate CTM integration in Africa as outlined in the WHO Traditional Medicine Strategy 2014–2023.