This research proposes a new strategy to generate the combinatorial test suite using Cuckoo Search concepts. Cuckoo Search is used for the design and implementation a strategy to construct optimized combinatorial sets. The strategy consists of different algorithms for construction in which they are combined to serve the Cuckoo Search. The new technique proved its efficiency and performance through different experiment sets, and obtained the most optimal size and duration time for five input-factors with degree of combination and each value equals three, gives (39 test cases) with time duration (0.12 second). Also, the effectiveness of the strategy is assessed by applying the generated test suites on a real-world case study for the purpose of functional testing. Results show that the generated test suites can detect faults effectively. Moreover, the strategy opens a new direction for the application of Cuckoo Search in the context of software engineering.