Opportunistic bacteria Staphylococcus aureus and Staphylococcus epidermidis often form rigid biofilms on tissues and inorganic surfaces. In the biofilm bacterial cells are embedded in a self-produced polysaccharide matrix and thereby are inaccessible to biocides, antibiotics, or host immune system. Here we show the antibacterial activity of newly synthesized cationic biocides, the quaternary ammonium, and bisphosphonium salts of pyridoxine (vitamin B6) against biofilm-embedded Staphylococci. The derivatives of 6-hydroxymethylpyridoxine were ineffective against biofilm-embedded S. aureus and S. epidermidis at concentrations up to 64 μg/mL, although all compounds tested exhibited low MICs (2 μg/mL) against planktonic cells. In contrast, the quaternary ammonium salt of pyridoxine (N,N-dimethyl-N-((2,2,8-trimethyl-4H-[1,3]dioxino[4,5-c]pyridin-5-yl)methyl)octadecan-1-aminium chloride (3)) demonstrated high biocidal activity against both planktonic and biofilm-embedded bacteria. Thus, the complete death of biofilm-embedded S. aureus and S. epidermidis cells was obtained at concentrations of 64 and 16 μg/mL, respectively. We suggest that the quaternary ammonium salts of pyridoxine are perspective to design new synthetic antibiotics and disinfectants for external application against biofilm-embedded cells.