High rates of health complaints (HCs) with substantial variation are reported in different university populations, which can be linked to socio-demographic, lifestyle-related factors, and cultural differences. HCs can be categorized into distinct components. This study aimed to identify and compare underlying dimensions of HCs (HC components); to access and compare HC prevalence, and the associations between HC components, socio-demographic, lifestyle-related factors, and perceived stress in German and Chinese university students. Two health surveys were conducted among 5159 university students (1853 Chinese, 3306 German). Factor analysis and logistic regression were applied. The prevalence of HC ranged from 4.6% to 40.2% over the two countries. Germans reported at least three HCs more often (47.2% vs. 35.8%). Chinese students more often reported gastrointestinal complaints. Perceived stress was positively associated with all three HC components in both countries (OR = 1.03–1.50) with stronger associations among Germans. Women more often reported HCs (OR = 1.32–2.43) with stronger associations among the Germans. Having a father with a low educational level was associated with high psychological symptoms among the Chinese (OR = 1.51), but with low gastrointestinal complaints among the Germans (OR = 0.79). The high prevalence of HCs in students requires country-specific interventions.