We present year-long, near-infrared (NIR) Hubble Space Telescope (HST) WFC3 observations of Mira variables in the water megamaser host galaxy NGC 4258. Miras are asymptotic giant branch variables that can be divided into oxygen- (O-) and carbon- (C-) rich subclasses. Oxygen-rich Miras follow a tight (scatter ̃0.14 mag) period-luminosity relation (PLR) in the NIR and can be used to measure extragalactic distances. The water megamaser in NGC 4258 gives a geometric distance to the galaxy accurate to 2.6% that can serve to calibrate the Mira PLR. We develop criteria for detecting and classifying O-rich Miras with optical and NIR data as well as NIR data alone. In total, we discover 438 Mira candidates that we classify with high confidence as O-rich. Our most stringent criteria produce a sample of 139 Mira candidates that we use to measure a PLR. We use the OGLE-III sample of O-rich Miras in the Large Magellanic Cloud to obtain a relative distance modulus, μ $_4258$ - μ $_LMC$ = 10.95 ± 0.01 (statistical) ±0.06 (systematic) mag, that is statistically consistent with the relative distance determined using Cepheids. These results demonstrate the feasibility of discovering and characterizing Miras using the NIR with the HST and the upcoming James Webb Space Telescope and using those Miras to measure extragalactic distances and determine the Hubble constant.