Collisionless shocks are shocks in which the mean-free path is much larger than the shock front. They are ubiquitous in astrophysics and the object of much current attention as they are known to be excellent particle accelerators that could be the key to the cosmic rays enigma. While the scenario leading to the formation of a fluid shock is well known, less is known about the formation of a collisionless shock. We present theoretical and numerical results on the formation of such shocks when two relativistic and symmetric plasma shells (pair or electron/proton) collide. As the two shells start to interpenetrate, the overlapping region turns Weibel unstable. A key concept is the one of trapping time τp, which is the time when the turbulence in the central region has grown enough to trap the incoming flow. For the pair case, this time is simply the saturation time of the Weibel instability. For the electron/proton case, the filaments resulting from the growth of the electronic and protonic Weibel instabilities, need to grow further for the trapping time to be reached. In either case, the shock formation time is 2τp in two-dimensional (2D), and 3τp in 3D. Our results are successfully checked by particle-in-cell simulations and may help designing experiments aiming at producing such shocks in the laboratory.