A series of novel quaternary ammonium 4-deoxypyridoxine derivatives was synthesized. Two compounds demonstrated excellent activity against a panel of Gram-positive methicillin-resistant S. aureus strains with MICs in the range of 0.5-2 μg/mL, exceeding the activity of miramistin. At the same time, both compounds were inactive against the Gram-negative E. coli and P. aeruginosa strains. Cytotoxicity studies on human skin fibroblasts and embryonic kidney cells demonstrated that the active compounds possessed similar toxicity with benzalkonium chloride but were slightly more toxic than miramistin. SOS-chromotest in S. typhimurium showed the lack of DNA-damage activity of both compounds; meanwhile, one compound showed some mutagenic potential in the Ames test. The obtained results make the described chemotype a promising starting point for the development of new antibacterial therapies.