As part of an effort to develop stable and replicable unnatural base pairs, we have evaluated a large number of unnatural nucleotides with predominantly hydrophobic nucleobases. Despite its limited aromatic surface area, a nucleobase analog scaffold that has emerged as being especially promising is the simple phenyl ring. Modifications of this scaffold with methyl and fluoro groups have been shown to impact base pair stability and polymerase recognition, suggesting that nucleobase shape, hydrophobicity and electrostatics are important. To further explore the impact of heteroatom substitution within this nucleobase scaffold, we report the synthesis, stability and polymerase recognition of nucleoside analogs bearing single bromo- or cyano-derivatized phenyl rings. Both modifications are found to generally stabilize base pair formation to a greater extent than methyl or fluoro substitution. Moreover, polymerase recognition of the unnatural base pairs is found to be very sensitive to both the position and nature of the heteroatom substituent. The results help identify the determinants of base pair stability and efficient replication and should contribute to the effort to develop stable and replicable unnatural base pairs.