The usage of nondestructive testing on early-aged concrete leads to enhacned safty and allows effective scheduling of construction, thus making it possible to maximize the time and cost efficiencies. In this study, a reliable nondestructive strength evaluation method for early-aged concrete using the longitudinal wave velocity is proposed. Compression tests were performed to examine factors influencing the velocity-strength relationship of concrete, such as water-cement (w/c) ratio, fine aggregate ratio, curing temperature, and curing condition. The test results show that a change in the w/c ratio and curing temperature has minor effect on the velocity-strength relationship/ However, curing condition significantly influences the velocity-strength relationship of early-aged concrete. Moreover, the longitudinal wave velocity increases with decreasing fine aggregate ratio. It is concluded from this study that the strength evaluation of early-age concrete can be achieved by a nonlinear equation which considers the effects of curing condition and fine aggregate ratio.