don't know your code but due to namespaces you may have to write:

\Predis\Client::...

and did you register Predis in your config/app ?

This error appears somewhere before my code.

at HandleExceptions->fatalExceptionFromError(array('type' => '1', 'message' => 'Class 'Predis\Client' not found', 'file' => '/vendor/laravel/framework/src/Illuminate/Redis/Database.php', 'line' => '58'

This string in config/app should work with Redis:

'Illuminate\Redis\RedisServiceProvider',

As far as I know there is no need to register it somehow else.. Documentatios says that I need to install it with composer and thats it.

Add "predis/predis": "~1.1@dev", to the "require" block in composer.json.

i.e:

{
    "name": "laravel/laravel",
    "description": "The Laravel Framework.",
    "keywords": ["framework", "laravel"],
    "license": "MIT",
    "type": "project",
    "require": {
        "laravel/framework": "5.0.*",
        "predis/predis": "~1.1@dev"
    },

    ...

}

I get this error Class 'App\Http\Controllers\Predis\Client' not found on my Controller.
In the Controller I simply call

    $client = new Predis\Client();
    $client->set('foo', 'bar');
    $value = $client->get('foo');

and Predis is not recognized. Do I need to add something more after I did a composer require Predis?

Btw I did 'predis/predis' : '1.0' as well as 'predis/predis' : '1.1@dev' AND I do have the Predis director in my vendor directory......