In implementations of systems for generating accessible color themes, a computing device implements an accessibility system to receive an input color palette including original colors defined in a color space. The accessibility system generates color vision deficiency simulations that correspond to pairs of the original colors and computes perceptual color differences between the color vision deficiency simulations. Candidate colors are determined for corresponding original colors based at least partially on the perceptual color differences and a conflicting perceptual color difference. The accessibility system outputs an output color palette including replacement colors defined in the color space that are generated at least partially based on distances between the candidate colors and the corresponding original colors computed in a CIELAB color space.