Eukaryotes duplicate their genomes using multiple replication origins, but the organization of origin firing along chromosomes and during S-phase is not well understood. Using fission yeast, we report the first genome-wide analysis of the spatial and temporal organization of replication origin firing, analyzed using single DNA molecules that can approach the full length of chromosomes. At S-phase onset, origins fire randomly and sparsely throughout the chromosomes. Later in S-phase, clusters of fired origins appear embedded in the sparser regions, which form the basis of nuclear replication foci. The formation of clusters requires proper histone methylation and acetylation, and their locations are not inherited between cell cycles. The rate of origin firing increases gradually, peaking just before mid S-phase. Toward the end of S-phase, nearly all the available origins within the unreplicated regions are fired, contributing to the timely completion of genome replication. We propose that the majority of origins do not fire as a part of a deterministic program. Instead, origin firing, both individually and as clusters, should be viewed as being mostly stochastic.