diff --git a/libempathy-gtk/empathy-images.h b/libempathy-gtk/empathy-images.h
index c714f04..d5fa536 100644
--- a/libempathy-gtk/empathy-images.h
+++ b/libempathy-gtk/empathy-images.h
@@ -24,12 +24,14 @@
 
 G_BEGIN_DECLS
 
-#define EMPATHY_IMAGE_OFFLINE             "empathy-offline"
-#define EMPATHY_IMAGE_HIDDEN              "empathy-offline"
-#define EMPATHY_IMAGE_AVAILABLE           "empathy-available"
-#define EMPATHY_IMAGE_BUSY                "empathy-busy"
-#define EMPATHY_IMAGE_AWAY                "empathy-away"
-#define EMPATHY_IMAGE_EXT_AWAY            "empathy-extended-away"
+#define EMPATHY_IMAGE_OFFLINE             "user-offline"
+/* user-invisible is not (yet?) in the naming spec but already implemented by
+ * some theme */
+#define EMPATHY_IMAGE_HIDDEN              "user-invisible"
+#define EMPATHY_IMAGE_AVAILABLE           "user-available"
+#define EMPATHY_IMAGE_BUSY                "user-busy"
+#define EMPATHY_IMAGE_AWAY                "user-away"
+#define EMPATHY_IMAGE_EXT_AWAY            "user-idle"
 #define EMPATHY_IMAGE_UNKNOWN             "empathy-pending"
 
 #define EMPATHY_IMAGE_MESSAGE             "im-message"
diff --git a/libempathy-gtk/empathy-ui-utils.c b/libempathy-gtk/empathy-ui-utils.c
index dcba5fe..9813c83 100644
--- a/libempathy-gtk/empathy-ui-utils.c
+++ b/libempathy-gtk/empathy-ui-utils.c
@@ -193,8 +193,8 @@ empathy_builder_unref_and_keep_widget (GtkBuilder *gui,
 	return widget;
 }
 
-const gchar *
-empathy_icon_name_for_presence (TpConnectionPresenceType presence)
+static const gchar *
+standard_icon_name_for_presence (TpConnectionPresenceType presence)
 {
 	switch (presence) {
 	case TP_CONNECTION_PRESENCE_TYPE_AVAILABLE:
@@ -206,7 +206,13 @@ empathy_icon_name_for_presence (TpConnectionPresenceType presence)
 	case TP_CONNECTION_PRESENCE_TYPE_EXTENDED_AWAY:
 		return EMPATHY_IMAGE_EXT_AWAY;
 	case TP_CONNECTION_PRESENCE_TYPE_HIDDEN:
-		return EMPATHY_IMAGE_HIDDEN;
+		if (gtk_icon_theme_has_icon (gtk_icon_theme_get_default (),
+					     EMPATHY_IMAGE_HIDDEN))
+			return EMPATHY_IMAGE_HIDDEN;
+
+		/* The 'hidden' icon is not an official one so we fallback to offline if
+		 * it's not implemented */
+		return EMPATHY_IMAGE_OFFLINE;
 	case TP_CONNECTION_PRESENCE_TYPE_OFFLINE:
 	case TP_CONNECTION_PRESENCE_TYPE_ERROR:
 	case TP_CONNECTION_PRESENCE_TYPE_UNKNOWN:
@@ -218,6 +224,48 @@ empathy_icon_name_for_presence (TpConnectionPresenceType presence)
 	return NULL;
 }
 
+static const gchar *
+fallback_icon_name_for_presence (TpConnectionPresenceType presence)
+{
+	switch (presence) {
+	case TP_CONNECTION_PRESENCE_TYPE_AVAILABLE:
+		return "empathy-available";
+	case TP_CONNECTION_PRESENCE_TYPE_BUSY:
+		return "empathy-busy";
+	case TP_CONNECTION_PRESENCE_TYPE_AWAY:
+		return "empathy-away";
+	case TP_CONNECTION_PRESENCE_TYPE_EXTENDED_AWAY:
+		return "empathy-extended-away";
+	case TP_CONNECTION_PRESENCE_TYPE_HIDDEN:
+		return "empathy-offline";
+	case TP_CONNECTION_PRESENCE_TYPE_OFFLINE:
+	case TP_CONNECTION_PRESENCE_TYPE_ERROR:
+	case TP_CONNECTION_PRESENCE_TYPE_UNKNOWN:
+		return "empathy-offline";
+	case TP_CONNECTION_PRESENCE_TYPE_UNSET:
+		return NULL;
+	}
+
+	return NULL;
+}
+
+const gchar *
+empathy_icon_name_for_presence (TpConnectionPresenceType presence)
+{
+	const gchar *name;
+
+	name = standard_icon_name_for_presence (presence);
+	if (name == NULL)
+		return NULL;
+
+	if (gtk_icon_theme_has_icon (gtk_icon_theme_get_default (), name))
+		return name;
+
+	/* The icon theme doesn't implement status icons; use the Empathy ones */
+	name = fallback_icon_name_for_presence (presence);
+	return name;
+}
+
 const gchar *
 empathy_icon_name_for_contact (EmpathyContact *contact)
 {
