We report the first APOGEE metallicities and α-element abundances measured for 3600 red giant stars spanning a large radial range of both the Large (LMC) and Small Magellanic Clouds, the largest Milky Way (MW) dwarf galaxies. Our sample is an order of magnitude larger than that of previous studies and extends to much larger radial distances. These are the first results presented that make use of the newly installed southern APOGEE instrument on the du Pont telescope at Las Campanas Observatory. Our unbiased sample of the LMC spans a large range in metallicity, from [Fe/H] = -0.2 to very metal-poor stars with [Fe/H] ≍ -2.5, the most metal-poor Magellanic Cloud (MC) stars detected to date. The LMC [α/Fe]-[Fe/H] distribution is very flat over a large metallicity range but rises by ∼0.1 dex at -1.0 < [Fe/H] ≲ -0.5. We interpret this as a sign of the known recent increase in MC star formation activity and are able to reproduce the pattern with a chemical evolution model that includes a recent "starburst." At the metal-poor end, we capture the increase of [α/Fe] with decreasing [Fe/H] and constrain the "α-knee" to [Fe/H] ≲ -2.2 in both MCs, implying a low star formation efficiency of ∼0.01 Gyr-1. The MC knees are more metal-poor than those of less massive MW dwarf galaxies such as Fornax, Sculptor, or Sagittarius. One possible interpretation is that the MCs formed in a lower-density environment than the MW, a hypothesis that is consistent with the paradigm that the MCs fell into the MW's gravitational potential only recently.