The phenothiazine system was identified as a favorable cap group for potent and selective histone deacetylase 6 (HDAC6) inhibitors. Here, we report the preparation and systematic variation of phenothiazines and their analogues containing a benzhydroxamic acid moiety as the zinc-binding group. We evaluated their ability to selectively inhibit HDAC6 by a recombinant HDAC enzyme assay, by determining the protein acetylation levels in cells by western blotting (tubulin vs histone acetylation), and by assessing their effects on various cancer cell lines. Structure-activity relationship studies revealed that incorporation of a nitrogen atom into the phenothiazine framework results in increased potency and selectivity for HDAC6 (more than 500-fold selectivity relative to the inhibition of HDAC1, HDAC4, and HDAC8), as rationalized by molecular modeling and docking studies. The binding mode was confirmed by co-crystallization of the potent azaphenothiazine inhibitor with catalytic domain 2 from Danio rerio HDAC6.