Intensive research in the area of medical nanotechnology, especially to cope with the bacterial resistance against conventional antibiotics, has shown strong antimicrobial action of metallic and metal-oxide nanomaterials towards a wide variety of bacteria. However, the important remaining problem is that nanomaterials with highest antibacterial activity generally express also a high level of cytotoxicity for mammalian cells. Here we present gallium nanoparticles as a new solution to this problem. We developed a nanocomposite from bioactive hydroxyapatite nanorods (84 wt %) and antibacterial nanospheres of elemental gallium (16 wt %) with mode diameter of 22 ± 11 nm. In direct comparison, such nanocomposite with gallium nanoparticles exhibited better antibacterial properties against Pseudomonas aeruginosa and lower in-vitro cytotoxicity for human lung fibroblasts IMR-90 and mouse fibroblasts L929 (efficient antibacterial action and low toxicity from 0.1 to 1 g/L) than the nanocomposite of hydroxyapatite and silver nanoparticles (efficient antibacterial action and low toxicity from 0.2 to 0.25 g/L). This is the first report of a biomaterial composite with gallium nanoparticles. The observed strong antibacterial properties and low cytotoxicity make the investigated material promising for the prevention of implantation-induced infections that are frequently caused by P. aeruginosa.