Highly stretchable sensors that can detect large strains are useful in deformable systems, such as soft robots and wearable devices. For stretchable strain sensors, two types of sensing methods exist, namely, resistive and capacitive. Capacitive sensing has several advantages over the resistive type, such as high linearity, repeatability, and low hysteresis. However, the sensitivity (gauge factor) of capacitive strain sensors is theoretically limited to 1, which is much lower than that of the resistive-type sensors. The objective of this study is to improve the sensitivity of highly stretchable capacitive strain sensors by integrating hierarchical auxetic structures into them. Auxetic structures have a negative Poisson’s ratio that causes increase in change in capacitance with applied strains, and thereby improving sensitivity. In order to prove this concept, we fabricate and characterize two sensor samples with planar dimensions 60 mm × 16 mm. The samples have an acrylic elastomer (3M, VHB 4905) as the dielectric layer and a liquid metal (eutectic gallium-indium) for electrodes. On both sides of the sensor samples, hierarchical auxetic structures made of a silicone elastomer (Dow Corning, Sylgard 184) are attached. The samples are tested under strains up to 50% and the experimental results show that the sensitivity of the sensor with the auxetic structure exceeds the theoretical limit. In addition, it is observed that the sensitivity of this sensor is roughly two times higher than that of a sensor without the auxetic structure, while maintaining high linearity (R2 = 0.995), repeatability (≥104 cycles), and low hysteresis.