An electrochemical sensor for guanine and adenine using cyclodextrin-modified poly(N-acetylaniline) (PNAANI) on a carbon paste electrode has been developed. The oxidation mechanism of guanine and adenine on the surface of the electrode was investigated by cyclic voltammetry. It was found that the electrode processes are irreversible, pH dependent, and involve several reaction products. The electron transfer process occurs in consecutive steps with the formation of a strongly adsorbed intermediate on the electrode surface. Also, a new method for estimating the apparent formation constants of guanine and adenine with the immobilized cyclodextrins, through the change of surface coverage of studied analytes has been reported. Both guanine and adenine showed linear concentrations in the range of 0.1–10 μM by using differential pulse voltammetry, with an experimental limit of detection down to 0.05 μM. Linear concentration ranges of 2–150 μM for guanine and 6–104 μM for adenine have been found when cyclic voltammetry was used for determination of both analytes.