We show how to derive time implicit formulations of relaxation schemes for the Euler equations for real materials in several space dimensions. In the fully time explicit setting, the relaxation approach has been proved to provide efficient and robust methods. It thus becomes interesting to answer the open question of the time implicit extension of the procedure. A first natural extension of the classical time explicit strategy is shown to fail in producing discrete solutions which converge in time to a steady state. We prove that this first approach does not permit a proper balance between the stiff relaxation terms and the flux gradients. We then show how to achieve a well-balanced time implicit method which yields approximate solutions at a perfect steady state.