A series of 108 novel quaternary bis-ammonium pyridoxine derivatives carrying various substituents at the quaternary nitrogen’s and acetal carbon was synthesized. Thirteen compounds exhibited antibacterial and antifungal activity (minimum inhibitory concentration (MIC) 0.25–16 µg/mL) comparable or superior than miramistin, benzalkonium chloride, and chlorhexidine. A strong correlation between the lipophilicity and antibacterial activity was found. The most active compounds had logP values in the range of 1–3, while compounds with logP > 6 and logP < 0 were almost inactive. All active compounds demonstrated cytotoxicity comparable with miramistin and chlorhexidine on HEK-293 cells and were three-fold less toxic when compared to benzalkonium chloride. The antibacterial activity of leading compound 5c12 on biofilm-embedded Staphylococcus aureus, Staphylococcus epidermidis, Escherichia coli or Pseudomonas aeruginosa was comparable or even higher than that of the benzalkonium chloride. In vivo 5c12 was considerably less toxic (LD50 1705 mg/kg) than benzalkonium chloride, miramistine, and chlorhexidine at oral administration on CD-1 mice. An aqueous solution of 5c12 (0.2%) was shown to be comparable to reference drugs efficiency on the rat’s skin model. The molecular target of 5c12 seems to be a cellular membrane as other quaternary ammonium salts. The obtained results make the described quaternary bis-ammonium pyridoxine derivatives promising and lead molecules in the development of the new antiseptics with a broad spectrum of antimicrobial activity.