A previous spectroscopic study identified the very massive O2 III star VFTS 16 in the Tarantula Nebula as a runaway star based on its peculiar line-of-sight velocity. We use the Gaia DR2 catalog to measure the relative proper motion of VFTS 16 and nearby bright stars to test if this star might have been ejected from the central cluster, R136, via dynamical ejection. We find that the position angle and magnitude of the relative proper motion (0.338 +/- 0.046 mas/yr, or approximately 80 +- 11 km/s) of VFTS 16 are consistent with ejection from R136 approximately 1.5 +/- 0.2 Myr ago, very soon after the cluster was formed. There is some tension with the presumed age of VFTS 16 that, from published stellar parameters, cannot be greater than 0.9 +0.3/-0.2 Myr. Older ages for this star would appear to be prohibited due to the absence of He I lines in its optical spectrum, since this sets a firm lower limit on its effective temperature. The dynamical constraints may imply an unusual evolutionary history for this object, perhaps indicating it is a merger product. Gaia DR2 also confirms that another very massive star in the Tarantula Nebula, VFTS 72 (alias BI253; O2 III-V(n)((f*)), is also a runaway on the basis of its proper motion as measured by Gaia. While its tangential proper motion (0.392 +/-0.062 mas/yr or 93 +/-15 km/s) would be consistent with dynamical ejection from R136 approximately 1 Myr ago, its position angle is discrepant with this direction at the 2$sigma$ level. From their Gaia DR2 proper motions we conclude that the two ~100 solar mass O2 stars, VFTS 16 and VFTS72, are fast runaway stars, with space velocities of around 100 km/s relative to R136 and the local massive star population. The dynamics of VFTS16 are consistent with it having been ejected from R136, and this star therefore sets a robust lower limit on the age of the central cluster of ~1.3 Myr.