The angular size of a star is a critical factor in determining its basic properties. Together with the distance, it provides the physical diameter of the star which, when combined with the effective temperature derived from spectral measurements, can be used to yield luminosity and mass estimates. Direct measurement of stellar angular diameters is difficult: at interstellar distances stars are generally too small to resolve by any individual imaging telescope. This fundamental limitation can be overcome by studying the diffraction pattern in the shadow cast when an asteroid occults a star, but only if sufficiently well resolved in time and when the photometric uncertainty is smaller than the noise added by atmospheric scintillation. Atmospheric Cherenkov telescopes used for particle astrophysics observations have not generally been exploited for optical astronomy due to the modest optical quality of the mirror surface. However, their large mirror area makes them well suited for such high-time-resolution precision photometry measurements. Here we report two occultations of stars observed by the VERITAS Cherenkov telescopes with millisecond sampling, from which we are able to provide a direct measurement of the occulted stars’ angular diameter at the < 0.1 milliarcsecond scale. This is a resolution never achieved before with optical measurements and represents an order of magnitude improvement over the equivalent lunar occultation method. We compare the resulting stellar radius measurements with empirically derived estimates from temperature and brightness measurements, confirming the latter can be biased for stars with ambiguous stellar classifications.