The RNA-guided endonuclease Cas9 generates a double-strand break at DNA target sites complementary to the guide RNA and has been harnessed for the development of a variety of new technologies, such as genome editing. Here, we report the crystal structures of Campylobacter jejuni Cas9 (CjCas9), one of the smallest Cas9 orthologs, in complex with an sgRNA and its target DNA. The structures provided insights into a minimal Cas9 scaffold and revealed the remarkable mechanistic diversity of the CRISPR-Cas9 systems. The CjCas9 guide RNA contains a triple-helix structure, which is distinct from known RNA triple helices, thereby expanding the natural repertoire of RNA triple helices. Furthermore, unlike the other Cas9 orthologs, CjCas9 contacts the nucleotide sequences in both the target and non-target DNA strands and recognizes the 5′-NNNVRYM-3′ as the protospacer-adjacent motif. Collectively, these findings improve our mechanistic understanding of the CRISPR-Cas9 systems and may facilitate Cas9 engineering.