In 1864 Estrup entered the Landsting (upper chamber) as a member of the National Landowners' Party. As minister of the interior from 1865, he made major improvements in the railways and in Esbjerg harbour. He influenced the writing of the new constitution of July 1866, which gave landowners extensive power in the Landsting. Estrup then became the leader of a powerful conservative group known as Højre (“Right”) in the Landsting. In 1875, backed by the majority and by the king, Christian IX, he became prime minister and formed a government. The Right demanded large appropriations for defense, but the Folketing (lower chamber) rejected Estrup's motion on fortifications. His government was able to maintain itself in power by letting the king declare a provisional budget. The opposition, known as Venstre (“Left”), considered the measures unconstitutional; Estrup counteracted public unrest with police action and a stricter penal code.

Faced with the strength of the Right, the Left broke into factions. Thereafter the Right, under Estrup's leadership, controlled the government for nearly two decades. He carried through some social reforms with the help of the moderate Left, whose majority also supported the Financial Act of April 1894; this act contained grants for temporary military installations but repealed Estrup's earlier police and press measures. After Estrup resigned in 1894, he remained a prominent critic of the Left-controlled governments.