Common bean (Phaseolus vulgaris L.) is important in African diets for protein, iron (Fe), and zinc (Zn), but traditional cultivars have long cooking time (CKT), which increases the time, energy, and health costs of cooking. Genomic selection was used to predict genomic estimated breeding values (GEBV) for grain yield (GY), CKT, Fe, and Zn in an African bean panel of 358 genotypes in a two-stage analysis. In Stage 1, best linear unbiased estimates (BLUE) for each trait were obtained from 898 genotypes across 33 field trials in East Africa. In Stage 2, BLUE in a training population of 141 genotypes were used in a multivariate genomic analysis with genome-wide single nucleotide polymorphism data from the African bean panel. Moderate to high genomic heritability was found for GY (0.45 ± 0.10), CKT (0.50 ± 0.15), Fe (0.57 ± 0.12), and Zn (0.61 ± 0.13). There were significant favorable genetic correlations between Fe and Zn (0.91 ± 0.06), GY and Fe (0.66 ± 0.17), GY and Zn (0.44 ± 0.19), CKT and Fe (-0.57 ± 0.21), and CKT and Zn (-0.67 ± 0.20). Optimal contributions selection (OCS), based on economic index of weighted GEBV for each trait, was used to design crossing within four market groups relevant to East Africa. Progeny were predicted by OCS to increase in mean GY by 12.4%, decrease in mean CKT by 9.3%, and increase in mean Fe and Zn content by 6.9 and 4.6%, respectively, with low achieved coancestry of 0.032. Genomic selection with OCS will accelerate breeding of high-yielding, biofortified, and rapid cooking African common bean cultivars.