An algorithm is derived for a hyperelastic incompressible solid coupled with a Newtonian fluid. It is based on a Eulerian formulation of the full system in which the main variables are the velocities. After a fully implicit discretization in time it is possible to eliminate the displacements and solve a variational equation for the velocities and pressures only. The stability of the method depends heavily on the use of characteristic-Galerkin discretization of the total derivatives. For comparison with previous works, the method is tested on a three-dimensional (3D) clamped beam in a pipe filled with a fluid. Convergence is studied numerically on an axisymmetric case.