The effect of length scale on the vibration response of a single-layer graphene sheet embedded in an elastic medium is studied using nonlocal Mindlin plate theory. The elastic medium is modeled using both Winkler-type and Pasternak-type elastic foundations. An explicit solution is derived for the natural frequencies of the graphene sheet. Through the analytical solution it is found that the vibration response of graphene sheet concerning the length scale effects considerably different from the results obtained by the classical theories. In comparison with the classical plate theory, the nonlocal model showed that the natural frequency of the graphene sheet decreases for smaller lengths of graphene sheet, higher aspect ratios, greater values of nonlocal parameter and stiffer elastic foundations.