Summary: Swarm intelligence algorithms, which are developed for solving complex optimization problems designed by focusing on simulating the social behavior of one species of simple animals. However, simple animals utilize cooperation to work together that result in more complex and smarter behaviors. This paper proposes a novel population-based optimization paradigm for solving NP-hard problems called “Aphid-Ant Mutualism (AAM)” which is inspired by a unique relationship between aphids and ants’ species. This relationship is called ‘mutualism’. Despite the previous studies that the social behaviors of aphids and ants were simulated, AAM models mutual interaction among aphids and ants in nature. Thus, AAM has new features by incorporating heterogeneous individuals consisting of aphids and ants that live in various colonies together and have different decentralized learning behaviors and objectives. Inspired by nature, colony-based information exchange and using different search strategies including focusing on the individual’s personal knowledge, learning from other colony’s members and information sharing with adjacent colonies are used. This mutualism leads to converging to the global optimum and avoids premature convergence. Performance of AAM is assessed using statistical evaluation, convergence analysis, and a non-parametric Wilcoxon rank-sum test with a 5% significance degree on forty-one benchmarks selected from well-known functions of recent studies and more challenging benchmark functions called CEC 2014, CEC 2017 and also CEC-C06 2019 test suite. Statistical results and comparisons with other meta-heuristic algorithms demonstrate that the AAM algorithm provides promising and competitive outcomes. Furthermore, it can produce more accurate solutions with a faster convergence rate to the global optima.