Before the discovery of the first member of the Kuiper belt in 1992, the trans-Neptunian population was supposed to lie on a flat disk and each member would follow a barely eccentric orbit. While less conventional orbits for the trans-Neptunian objects were being discovered, our understanding of its orbital structure and origin was continually changed. A basic classification of the trans-Neptunian population as to their orbits identifies a classical low inclination Kuiper belt population, a resonant population, a high inclination Kuiper belt population, a scattered population and an extended population. Several mechanisms have been proposed to explain the orbital architecture of the Kuiper belt population. Presently, the most plausible scenarios are unequivocally related with the primordial planetary migration induced by a planetesimal disk. Low inclination orbits in the Kuiper belt may have been moderately pushed out from a dynamically cold primordial disk by the resonance sweeping mechanism. The origin of high inclination objects in the classical Kuiper belt is however to be found in a primordial Neptune scattered population, through a perihelion increasing mechanism based on secular resonances. Another push-out mechanism based on the sweeping of the 1:2 resonance with Neptune has also been invoked to explain the low inclination orbits in the classical Kuiper belt. Assuming these last two mechanisms, Kuiper belt objects do not need to have been formed in situ. This kind of formation process would demand a quite large original mass in the Kuiper belt region, which would have brought Neptune beyond its present position at 30 AU. Thus with the exception of the low inclination classical Kuiper belt objects and a few resonant ones, all other trans-Neptunian objects are present or past scattered objects. This notion also includes the case for Sedna, so far the only certain member of the extended population. In its most plausible formation scenario, it was a primordial scattered object by Neptune whose perihelion was increased by the close passage of a star.