This paper proposes a novel two-step strategy for testing the goodness-of-fit of parametric regression models in ultra-high dimensional sparse settings, where the predictor dimension far exceeds the sample size. This regime usually renders existing goodness-of-fit tests for regressions infeasible, primarily due to the curse of dimensionality or their reliance on the asymptotic linearity and normality of parameter estimators -- properties that may no longer hold under ultra-high dimensional settings. To address these limitations, our strategy first constructs multiple test statistics based on projected predictors from distinct projections and establishes their asymptotic properties under both the null and alternative hypotheses. This projection-based approach significantly mitigates the dimensionality problem, enabling our tests to detect local alternatives converging to the null at the rate as if the predictor were univariate. An important finding is that the resulting test statistics based on linearly independent projections are asymptotically independent under the null hypothesis. Based on this, our second step employs powerful $p$-value combination procedures, such as the minimum $p$-value and the Fisher combination of $p$-value, to form our final tests and enhance power. Theoretically, our tests only require the standard convergence rate of parameter estimators to derive their limiting distributions, thereby circumventing the need for asymptotic linearity or normality of parameter estimators. Simulations and real-data applications confirm that our approach provides robust and powerful goodness-of-fit testing in ultra-high dimensional settings.