An all-optical atomic Controlled-NOT (CNOT)/polarization gate operation is demonstrated with low light intensities in a room-temperature atomic medium. Using a Polarization-Selective-Kerr-Phase-Shift (PSKPS) technique, a
π phase shift is written to only one of the two circularly-polarized components of a linearly-polarized input signal field by a weak phase-control field with "magic" detuning. At the exit of the medium, the signal field maintains its original strength but acquires a 90
o linear polarization rotation, demonstrating the first fast, high-fidelity CNOT/polarization gate operation in a room-temperature atomic medium. This development opens the realm of possibilities for potential future extremely low light level telecommunication and information processing systems.