It is well known that the root-knot nematodes, Meloidogyne spp., incite and aggravate the diseases caused by fungal and bacterial pathogens. The synergistic effects of the inoculation of Meloidogyne incognita combined with Fusarium oxysporum f. sp. lycopersici showed the greatly increased wilt symptoms developed on tomato plants compared to the inoculation of either of the two pests alone. For the biological control of the complex disease, a variety of bacterial isolates were tested for antagonistic effects to select ones that had both nematicidal and antifungal activities. Among forty plant growth-promoting rhizobacteria (PGPR) tested, Paenibacillus polymyxa G508 and G462 and P. lentimorbus G158 showed strong antifungal and nematicidal activities against F. oxysporum f. sp. lycopersici and second-stage juveniles (J2) of M. incognita, respectively, and also inhibited egg hatch of the nematode. The addition of Paenibacillus strains into potted soil suppressed the Fusarium-wilt severity and root galling on tomato and increased plant growths. P. lentimorbus G158 were abundantly proliferated on tomato seeds and hypocotyls more than P. polymyxa G 462 and had no phytotoxic effect on tomato plant. Under the greenhouse conditions, seed treatment of P. lentimorbus G158 reduced wilt severity caused by Fusarium wilt-root knot disease complex and root gall formation and increased tomato growth compared to the untreated control. Root-galls caused by both pathogens treated with bacterial culture had fewer and smaller giant-cells than untreated control, and scanning electron microscopy revealed alteration and distortion of hyphal cell wall of F. oxysporum and lysis of M. incognita egg shell by the bacterial treatment. All of these results suggest the Paenibacillus strains, especially G158 may have a high potential developed as biological control agents for the complex disease.