For the initiation of DNA replication, dsDNA is unwound by helicases. Primases then recognize specific sequences on the template DNA strands and synthesize complementary oligonucleotide primers that are elongated by DNA polymerases in leading- and lagging-strand mode. The bacterial plasmid RSF1010 provides a model for the initiation of DNA replication, because it encodes the smallest known primase RepB' (35.9 kDa), features only 1 single-stranded primase initiation site on each strand (ssiA and ssiB, each 40 nt long with 5'- and 3'-terminal 6 and 13 single-stranded nucleotides, respectively, and nucleotides 7-27 forming a hairpin), and is replicated exclusively in leading strand mode. We present the crystal structure of full-length dumbbell-shaped RepB' consisting of an N-terminal catalytic domain separated by a long alpha-helix and tether from the C-terminal helix-bundle domain and the structure of the catalytic domain in a specific complex with the 6 5'-terminal single-stranded nucleotides and the C7-G27 base pair of ssiA, its single-stranded 3'-terminus being deleted. The catalytic domains of RepB' and the archaeal/eukaryotic family of Pri-type primases share a common fold with conserved catalytic amino acids, but RepB' lacks the zinc-binding motif typical of the Pri-type primases. According to complementation studies the catalytic domain shows primase activity only in the presence of the helix-bundle domain. Primases that are highly homologous to RepB' are encoded by broad-host-range IncQ and IncQ-like plasmids that share primase initiation sites ssiA and ssiB and high sequence identity with RSF1010.