We report on Fermi Large Area Telescope (LAT) and multi-wavelength results on the recently discovered very-high-energy (VHE, E > 100 GeV) blazar S4 0954+65 (z = 0.368) during an exceptionally bright optical flare in 2015 February. During the time period (2015 February 13/14, or MJD 57067) when the MAGIC telescope detected VHE γ-ray emission from the source, the Fermi-LAT data indicated a significant spectral hardening at GeV energies, with a power-law photon index of 1.8 ± 0.1-compared with the 3FGL (The Fermi LAT 4-Year Point Source Catalog) value (averaged over four years of observation) of 2.34 ± 0.04. In contrast, Swift X-Ray Telescope data showed a softening of the X-ray spectrum, with a photon index of 1.72 ± 0.08 (compared with 1.38 ± 0.03 averaged during the flare from MJD 57066 to 57077), possibly indicating a modest contribution of synchrotron photons by the highest-energy electrons superposed on the inverse Compton component. Fitting of the quasi-simultaneous (<1 d) broad-band spectrum with a one-zone synchrotron plus inverse-Compton model revealed that GeV/TeV emission could be produced by inverse-Compton scattering of external photons from the dust torus. We emphasize that a flaring blazar showing high flux of ≳1.0 × 10-6 photons cm-2 s-1 (E > 100 MeV) and a hard spectral index of ΓGeV < 2.0 detected by Fermi-LAT on daily timescales is a promising target for TeV follow-up by ground-based Cherenkov telescopes to discover high-redshift blazars, investigate their temporal variability and spectral features in the VHE band, and also constrain the intensity of the extragalactic background light.