Several planets have recently been discovered around old metal-poor stars, implying that these planets are also old, formed in the early Universe. The canonical theory suggests that the conditions for their formation could not have existed at such early epochs. In this paper we argue that the required conditions, such as sufficiently high dust-to-gas ratio, could in fact have existed in the early Universe immediately following the first episode of metal production in Pop. III stars, both in metal-enhanced and metal-deficient environments. Metal-rich regions may have existed in multiple isolated pockets of enriched and weakly-mixed gas close to the massive Pop. III stars. Observations of quasars at redshifts $zsim 5$, and gamma-ray bursts at $zsim 6$, show a very wide spread of metals in absorption from $rm [X/H]simeq -3$ to $simeq -0.5$. This suggests that physical conditions in the metal-abundant clumps could have been similar to where protoplanets form today. However, planets could have formed even in low-metallicity environments, where formation of stars is expected to proceed due to lower opacity at higher densities. In such cases, the circumstellar accretion disks are expected to rotate faster than their high-metallicity analogues. This can result in the enhancement of dust particles at the disk periphery, where they can coagulate and start forming planetesimals. In conditions with the low initial specific angular momentum, radiation from the central protostar can act as a trigger to drive instabilities with masses in the Earth to Jupiter mass range. Discoveries of planets around old metal-poor stars (e.g. HIP 11952, $rm [Fe/H]sim -1.95$) show that planets did indeed form in the early Universe and this may require modification of our understanding of the physical processes that produce them. This work is an attempt to provide a heuristic scenario for their existence.