Vibration-fatigue failure occurs when a structure is dynamically excited within its natural frequency range. Unlike metals, which have constant fatigue parameters, polymers can exhibit frequency-dependent fatigue parameters, significantly affecting the vibration resilience of 3D-printed polymer structures. This manuscript presents a study utilizing a novel vibration-fatigue testing methodology to characterize the frequency dependence of polymer material fatigue parameters under constant temperature conditions. In this investigation, 3D-printed PLA samples with frequency-tunable geometry were experimentally tested on an electro-dynamical shaker with a random vibration profile. Using the validated numerical models, the estimation of vibration-fatigue life was obtained and compared to the experimental results. Performing the numerical minimization of estimated and actual fatigue lives, the frequency-dependent fatigue parameters were assessed. In particular, the results indicate that the tested samples exhibit varying fatigue parameters within the loading frequency range of 250–750 Hz. Specifically, as the loading frequency increases, the fatigue exponent increases and fatigue strength decreases. These findings confirm the frequency dependence of fatigue parameters for 3D-printed polymer structures, underscoring the necessity of experimental characterization to reliably estimate the vibration-fatigue life of 3D-printed polymer structures. The utilization of the introduced approach therefore enhances the vibration resilience of the 3D-printed polymer mechanical component.