A multiscale computational method is developed to model the nanoscale viscoelasticity of fluids by bridging non-Markovian fluctuating hydrodynamics (FHD) and molecular dynamics (MD) simulations. To capture the elastic responses that emerge at small length scales, we attach an additional rheological model parallel to the macroscopic constitutive equation of a fluid. The widely used linear Maxwell model is employed as a working choice; other models can be used as well. For a fluid that is Newtonian in the macroscopic limit, this approach results in a parallel Newtonian-Maxwell model. For water, argon, and an ionic liquid, the power spectrum of momentum field autocorrelation functions of the parallel Newtonian-Maxwell model agrees very well with those calculated from all-atom MD simulations. To incorporate thermal fluctuations, we generalize the equations of FHD to work with non-Markovian rheological models and colored noise. The fluctuating stress tensor (white noise) is integrated in time in the same manner as its dissipative counterpart and numerical simulations indicate that this approach accurately preserves the set temperature in a FHD simulation. By mapping position and velocity vectors in the molecular representation onto field variables, we bridge the non-Markovian FHD with atomistic MD simulations. Through this mapping, we quantitatively determine the transport coefficients of the parallel Newtonian-Maxwell model for water and argon from all-atom MD simulations. For both fluids, a significant enhancement in elastic responses is observed as the wave number of hydrodynamic modes is reduced to a few nanometers. The mapping from particle to field representations and the perturbative strategy of developing constitutive equations provide a useful framework for modeling the nanoscale viscoelasticity of fluids.