A new numerical scheme for simulation of viscoelastic fluid flows was designed, making use of finite element algorithms generally regarded as advantageous for tackling the problem. This includes the Lagrangian approach for the solution of viscoelastic constitutive equation using the co-deformational frame of reference with a possibility of analytically solving the equation along the particles trajectories, which in turn allowed eluding the solution of any system of linear equations for the stress. Then, the full ellipticity of the momentum conservation equation was utilised thanks to a possibility of accurate determination of the stress tensor independently of the velocity field at the current stage of computation. The needed independent stress was calculated at each time step on the basis of the past deformation history, which in turn was determined on the basis of the past velocity fields, all incorporated into a modified Euler time stepping algorithm. Owing to explicit inclusion of the full viscous term from the viscoelastic model into the momentum conservation equation, no stress splitting was necessary. The trajectory feet tracking was done accurately using a semi-analytic solution of the displacement gradient evolution equation and a weak formulation of the kinematics equation, the latter at the expense of solving an extra symmetric system of linear equations. The error expressed in the form of the Sobolev norms was determined using a comparison with available analytical solution for UCM fluid in the transient regime or numerically obtained steady-state stress values for the PTT fluid in Couette flow. The implementation of the PTT fluid model was done by modifying the relative displacement gradient tensor so that a new convective frame was defined. The stability of the algorithm was assessed using the well-known benchmark problem of a sphere sedimenting in a tube with viscoelastic fluid. The stable numerical results were obtained at high Weissenberg numbers, with the limit of convergence Wi = 6.6, exceeding any previously reported values. The robustness of the code was proven by simulation of the Weissenberg effect (the rod-climbing phenomenon) with the use of PTT fluid.