Assuming the presence of physics beyond the Standard Model (SM) with a characteristic scale M ~ O(10) TeV, we investigate the naturalness of the Higgs sector at scales below M using an effective field theory (EFT) approach. We obtain the leading 1-loop EFT contributions to the Higgs mass with a Wilsonian-like hard cutoff, and determine the constraints on the corresponding operator coefficients for these effects to alleviate the little hierarchy problem up to the scale of the effective action Lambda < M, a condition we denote by EFT-naturalness. We also determine the types of physics that can lead to EFT-naturalness and show that these types of new physics are best probed in vector-boson and multiple-Higgs production. The current experimental constraints on these coefficients are also discussed.