The origin of the gas in between the Magellanic Clouds (MCs)—known as the "Magellanic Bridge" (MB)—is puzzling. Numerical simulations suggest that the MB formed from tidally stripped gas and stars in a recent interaction between the MCs. However, the apparent lack of stripped intermediate- or old-age stars associated with the MB is at odds with this picture. In this paper, we present the first results from the MAGellanic Inter-Cloud program (MAGIC) aimed at probing the stellar populations in the inter-Cloud region. We present observations of the stellar populations in two large fields located in between the Large and Small Magellanic Clouds (LMC/SMC), secured using the WFI camera on the 2.2 m telescope in La Silla. Using a synthetic color-magnitude diagram technique, we present the first quantitative evidence for the presence of intermediate-age and old stars in the inter-Cloud region. The intermediate-age stars—which make up ~28% of all stars in the region—are not present in fields at a similar distance from the SMC in a direction pointing away from the LMC. This provides potential evidence that these intermediate-age stars could have been tidally stripped from the SMC. However, spectroscopic studies will be needed to confirm or rule out the tidal origin for the inter-Cloud gas and stars.