The increment of the required lifetime for structural components commonly used in different machinery applications (aerospace, automotive, railway and energy applications) has recently led to a more detailed investigation on the Very-High-Cycle Fatigue (VHCF) response of metallic materials. Experimental tests showed that specimens made of high-strength steels may fail at stress amplitudes below the conventional fatigue limit (106-107 cycles) and that fatigue failures may be due to two different types of crack nucleation. If the stress amplitude is above the conventional fatigue limit, cracks nucleate at the specimen surface; if the stress amplitude is below the conventional fatigue limit, cracks nucleate from inclusions or internal defects (internal nucleation) and failures occur at very high number of cycles (up to 1010 cycles). The VHCF response of high-strength steels is therefore significantly influenced by the inclusion population (inclusion dimension and quantity). In the present paper, the VHCF response of an Örvar Supreme steel characterized by a high level of cleanliness was investigated. Fully reversed tension-compression tests were carried out with an ultrasonic testing machine capable to reach a loading frequency equal to 20 kHz (ultrasonic tests) and allowing for a significant reduction of the testing time (109 cycles in 14 hours). Fracture surfaces were observed through a Scanning Electron Microscope. Experimental results showed that, even with a high-strength steel characterized by a high level of cleanliness, VHCF failures indeed occur and internal nucleation of cracks must be taken into account in order to prevent unexpected failures at stress amplitudes below the conventional fatigue limit.