El equipo nace en 1977, gracias a una iniciativa del periodista radiofónico José María García. En un principio se llamó Hora XXV, como el programa informativo nocturno de la Cadena SER, y se ideó para jugar partidos benéficos y de exhibición. La plantilla estaba formada por antiguos jugadores de fútbol, como Amancio o Ufarte, y periodistas entre los cuales se encontraba el propio García.

En 1979 la Federación Española de Fútbol organizó el primer campeonato oficial de fútbol sala, y participó en la temporada inicial como Interviú Hora XXV. El club se proclamó campeón en su debut. En 1981 El Corte Inglés selló un acuerdo de patrocinio, por lo que el equipo cambió su nombre por Interviú Lloyd's y posteriormente Interviú Boomerang. En la década de 1980 obtienen ocho ligas. Durante toda su historia, el club jugó en Madrid, Alcobendas, Alcalá de Henares y Torrejón de Ardoz.

En 1986 participó en la primera edición del Campeonato Mundial de Clubes de Futsal, disputado en Río de Janeiro. El conjunto español venció en 3 partidos, pero empató con Peñarol de Uruguay y cayó ante el anfitrión Bradesco por 2 a 1 obteniendo el segundo lugar en el torneo.

En 1989 la Federación Española de Fútbol y la Asociación de Fútbol Sala unificaron sus campeonatos, creando así la Liga Nacional de Fútbol Sala. Interviú fue uno de sus miembros fundadores, y en la temporada inaugural los madrileños consiguieron la Liga y Copa de España con un gran equipo en el que destacaba Ramón Carosini. Dos años después, Interviú se proclamó campeón de Europa por primera vez. En los siguientes años el club mantuvo un buen nivel, pero la dura competencia no les permitió conseguir la liga de nuevo hasta 1996.

Desde 2002 hasta 2005, con Jesús Candelas como entrenador, y destacando algunos de los mejores jugadores de este deporte, como Schumacher o Luis Amado,6​ Interviú consiguió cuatro títulos de liga consecutivos y se convirtió en uno de los dominadores del campeonato nacional. Además, el club ganó tres veces consecutivas la Copa Intercontinental y fue el primer equipo que obtuvo todos los títulos oficiales existentes en este deporte a nivel europeo. En reconocimiento, el Gobierno de España otorgó a la institución la Placa de Oro de la Real Orden del Mérito Deportivo en 2006.

Cuando la constructora Fadesa quebró, el equipo firmó un acuerdo de patrocinio con el operador móvil Movistar. Tras estar varios años desvinculado de Grupo Zeta e Interviú, la institución cambió su nombre por Inter Fútbol Sala en octubre de 2010.7​ En la temporada 2013-14, el club ficha al jugador Ricardinho (considerado por muchos el mejor jugador de la historia del fútbol sala8​), confeccionando a su alrededor un equipo que dominaría durante el siguiente lustro el panorama nacional y europeo, manteniéndose en el equipo hasta su marcha en 2020, tras alzar el Inter su decimocuarto título de la LNFS en la "eliminatoria exprés" realizada por el coronavirus, en el que ya no participaría el jugador por desavenencias con el club.

A partir de la temporada 2015-16, el Inter Movistar disputa sus partidos en Torrejón de Ardoz debido al mal estado de las instalaciones de Alcalá.

El 1 de julio de 2020 y tras ganar la liga, el club cursa la baja como asociado de la LNFS de la que formaba parte como fundador. Las discrepancias públicas de José María García con la gestión de Javier Lozano hacen que Movistar Inter se una a otros clubes que quieren que el fútbol sala español esté organizado por la RFEF.

Mantiene una fuerte rivalidad con el ElPozo Murcia, con quien disputa el clásico del fútbol sala. Y también con el FC Barcelona Lassa, otro de los equipos más laureados del país. En sentido contrario, mantiene una buena relación con el club de fútbol Atlético de Madrid, con quien suscribió un acuerdo de colaboración en 2017.