En principio debería funcionar. Verifica si la consulta realmente selecciona algún registro:
Código SQL
[-]SELECT * FROM HISTORIA
where
ID_CLIENTE IN (SELECT ID_CLIENTE FROM CLIENTES WHERE fecha < '01/01/2015')
AND ID_HISTORIA IN (SELECT ID_HISTORIA FROM CLIENTES WHERE fecha < '01/01/2015')
Lo otro es dotar a las tablas de los índices adecuados, si no los tiene y si la consulta va a ser repetitiva.