To further reduce the power dissipation in nanoscale transistors, the fundamental limit posed by the Boltzmann distribution of electrons has to be overcome. Stabilization of negative capacitance in a ferroelectric gate insulator can be used to achieve this by boosting the transistor gate voltage. Up to now, negative capacitance is only directly observed in polymer and perovskite ferroelectrics, which are incompatible with semiconductor manufacturing. Recently discovered HfO2-based ferroelectrics, on the other hand, are ideally suited for this application because of their high scalability and semiconductor process compatibility. Here, for the first time, a direct measurement of negative capacitance in polycrystalline HfO2-based thin films is reported. Decreasing voltage with increasing charge transients are observed in 18 and 27 nm thin Gd:HfO2 capacitors in series with an external resistor. Furthermore, a multigrain Landau-Khalatnikov model is developed to successfully simulate this transient behavior in polycrystalline ferroelectrics with nucleation limited switching dynamics. Structural requirements for negative capacitance in such materials are discussed. These results demonstrate that negative capacitance effects are not limited to epitaxial ferroelectrics, thus significantly extending the range of potential applications.