Background: Risk stratification based on pre-test probability may improve the diagnostic accuracy of temporal artery high-resolution compression sonography (hrTCS) in the diagnostic workup of cranial giant cell arteritis (cGCA). Methods: A logistic regression model with candidate items was derived from a cohort of patients with suspected cGCA (n = 87). The diagnostic accuracy of the model was tested in the derivation cohort and in an independent validation cohort (n = 114) by receiver operator characteristics (ROC) analysis. The clinical items were composed of a clinical prediction rule, integrated into a stepwise diagnostic algorithm together with C-reactive protein (CRP) values and hrTCS values. Results: The model consisted of four clinical variables (age > 70, headache, jaw claudication, and anterior ischemic optic neuropathy). The diagnostic accuracy of the model for discrimination of patients with and without a final clinical diagnosis of cGCA was excellent in both cohorts (area under the curve (AUC) 0.96 and AUC 0.92, respectively). The diagnostic algorithm improved the positive predictive value of hrCTS substantially. Within the algorithm, 32.8% of patients (derivation cohort) and 49.1% (validation cohort) would not have been tested by hrTCS. None of these patients had a final diagnosis of cGCA. Conclusion: A diagnostic algorithm based on a clinical prediction rule improves the diagnostic accuracy of hrTCS.