The yield and protein performance in a soybean genotype result from its interaction with the prevailing environmental conditions. This makes selecting the best genotypes under varied target production environments more complex. This study’s objectives were to determine protein content and protein stability of 30 elite soybean genotypes in major soybean-growing areas of Uganda, assess the yield performance and stability in soybeans and determine the relationship between the protein content and grain yield in soybeans. The genotypes were planted in a randomized complete block design of three replications for six seasons across eight locations in Uganda. Genotype and genotype-by-environment (GGE) biplot analyses classified the test locations into three mega-environments for soybean protein and grain yields. Genotype NII X GC 20.3 had the highest mean protein content of 43.0%, and BSPS 48A-9-2 and BSPS 48A-28 were superior for the mean grain yield (1207 kg ha−1). Bulindi was the most discriminating and representative test environment for soybean yield. A weak and negative correlation (r = −0.1**, d.f. = 29) was detected between the protein content (%) and yield (kg ha−1). The highest-yielding genotypes BSPS 48A-9-2, BSPS 48A-31, and Nam II × GC 44.2 are recommended for further evaluation under farmers’ production conditions for selection and release as new soybean varieties in Uganda.