The present invention is aimed to provide means and methods for recovery of an IP Multimedia Subsystem ‘IMS’ where a Home Subscriber Server ‘HSS’ holding subscriber data for subscribers of the IMS has suffered a restart. A first method of recovery is applied after detecting a HSS restart, and as receiving a registration from a given subscriber or an invitation to communicate with a given subscriber from another subscriber. A second method of recovery is applied after detecting a HSS restart, and as receiving a request from a given subscriber at a S-CSCF previously assigned for serving the given subscriber in the IMS. Both first and second methods may be applied in the IMS separately, or in cooperation, following a best effort to ensure that, whatever event occurs first, receiving a registration from a given subscriber, or an invitation to communicate with a given subscriber, or receiving a request from a given subscriber at a S-CSCF previously assigned, the actions triggered by the first method or by the second method achieve the recovery of the IMS without further actions not applied yet from said second or first methods.