We find that the initial dust masses in planetary debris disks are correlated with the metallicities of their central stars. We compiled a large sample of systems, including Spitzer, the Herschel DUNES and DEBRIS surveys, and WISE debris disk candidates. We also merged 33 metallicity catalogs to provide homogeneous [Fe/H] and {sigma}_[Fe/H]_ values. We analyzed this merged sample, including 222 detected disks (74 warm and 148 cold) around a total of 187 systems (some with multiple components) and 440 disks with only upper limits (125 warm and 315 cold) around a total of 360 systems. The disk dust masses at a common early evolutionary point in time were determined using our numerical disk evolutionary code, evolving a unique model for each of the 662 disks backward to an age of 1Myr. We find that disk-bearing stars seldom have metallicities less than [Fe/H]=-0.2 and that the distribution of warm component masses lacks examples with large mass around stars of low metallicity ([Fe/H]<-0.085). Previous efforts to find a correlation have been largely unsuccessful; the primary improvements supporting our result are (1) basing the study on dust masses, not just infrared excess detections; (2) including upper limits on dust mass in a quantitative way; (3) accounting for the evolution of debris disk excesses as systems age; (4) accounting fully for the range of uncertainties in metallicity measurements; and (5) having a statistically large enough sample.