We report on the detection of variable stars in the Canes Venatici II (CVn II) dwarf spheroidal galaxy, a new satellite of the Milky Way recently discovered by the Sloan Digital Sky Survey. We also present a V, B-V color-magnitude diagram that reaches V = 25.5 mag, showing the galaxy's main sequence turn off at V = 24.5 mag and revealing several candidate blue straggler stars. Two RR Lyrae stars have been identified within the half-light radius of CVn II,a fundamental-mode variable (RRab) with period P_ab = 0.743 days, and a first-overtone (RRc) RR Lyrae star with P_c = 0.358 days. The rather long periods of these variables along with their position on the period-amplitude diagram support an Oosterhoff type II classification for CVn II. The average apparent magnitude of the RR Lyrae stars, = 21.48 +/- 0.02 mag, is used to obtain a precision distance modulus of mu_0 = 21.02 +/- 0.06 mag and a corresponding distance of 160(+4,-5} kpc, for an adopted reddening E(B-V) = 0.015 mag. Comment: Submitted to ApJ Letters