The Sun was about thirty percent dimmer when the Earth was young, which should have left the planet frozen solid. The geological record shows liquid water and life instead. What kept the early Earth warm has been argued about since 1972 and is not settled.
Stellar evolution is well understood and the Sun's brightening is not in doubt. As hydrogen fuses to helium in the core, the core contracts and heats, and the fusion rate rises. Models put solar output at roughly seventy percent of its present value four billion years ago, rising steadily since.

With the present atmosphere and that output, the Earth's average temperature would have been below freezing until around two billion years ago. Ice would have raised the planet's reflectivity, reflecting more sunlight and driving further cooling, so an early freeze should have been self-sustaining and difficult to escape.
The geological record says otherwise. Sedimentary rocks laid down in water date to at least 3.8 billion years ago. Zircon crystals from 4.4 billion years ago carry oxygen isotope signatures indicating they formed in the presence of liquid water. Stromatolites, layered structures built by microbial mats, date to around 3.5 billion years.

Carl Sagan and George Mullen posed the contradiction formally in 1972.
The obvious answer is a stronger greenhouse effect, and the argument is about which gas and how much.
Carbon dioxide is the leading candidate and has a self-regulating mechanism behind it. Silicate weathering removes carbon dioxide from the atmosphere and the reaction runs faster when it is warmer and wetter, so a warm planet draws its own greenhouse gas down and a cold one accumulates it from volcanic output. This carbonate-silicate cycle acts as a thermostat over geological time.
The difficulty is quantitative. Compensating for a thirty percent dimmer Sun requires carbon dioxide at a few hundred times present levels, and several lines of geological evidence argue against concentrations that high. Palaeosols, ancient soils, contain minerals whose stability constrains the carbon dioxide of the air they formed in, and the constraints come out below what is needed. The absence of siderite in some formations where high carbon dioxide would produce it is a further argument.
Methane is the main alternative. It is a far stronger greenhouse gas per molecule, and before oxygen accumulated it would have persisted much longer in the atmosphere. Methanogenic archaea are among the earliest life forms and would have produced it in quantity. The problem is that at high concentrations methane forms an organic haze that reflects sunlight, which cools rather than warms, setting a ceiling on how much can help.
Lower reflectivity is a different approach. With less continental crust exposed and fewer cloud condensation nuclei, the early Earth may have absorbed more of the sunlight that reached it. Some models find a substantial share of the required warming from this alone.
Nitrogen pressure broadening is a subtler proposal: a denser nitrogen atmosphere would widen the absorption lines of greenhouse gases and increase their effect. Estimates of early atmospheric pressure vary and some evidence, from the size of raindrop impressions in ancient ash, suggests pressure was not higher.

Most current work favours a combination rather than a single cause: moderately elevated carbon dioxide, some methane, lower reflectivity, and possibly other contributions, together sufficient without any one being pushed past what the evidence allows.
That is a reasonable position and it is also unsatisfying, because a combination with several adjustable contributions is difficult to test. The constraints on each individual factor are loose enough that many combinations work.
Some researchers argue the geological constraints on carbon dioxide are weaker than claimed, which would reduce the problem substantially. Others argue the solar models slightly overstate the dimming.
The paradox is a test case for climate models. A model that cannot reproduce a planet known to have been habitable, under conditions that are reasonably well constrained, is a model with a gap.
It also bears directly on habitability elsewhere. All stars brighten as they age, so any planet keeping liquid water for billions of years must have a mechanism that compensates. The carbonate-silicate thermostat is currently the best candidate, and whether it operates on planets without plate tectonics is unknown and consequential for how many worlds could hold water long enough for life to arise.