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-1, or approximately 80±11 km s-1) 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 BI 253; 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-1 or 93±15 km s-1) would be consistent with dynamical ejection from R136 approximately 1 Myr ago, its position angle is discrepant with this direction at the 2σ level. From their Gaia DR2 proper motions we conclude that the two ˜100 M⊙ O2 stars, VFTS 16 and VFTS 72, are fast runaway stars, with space velocities of around 100 km s-1 relative to R136 and the local massive star population. The dynamics of VFTS 16 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.