Laravel Eloquent - firstOrCreate() on a relationship

This should do:

Client::find($id)->first()->users()->firstOrCreate(array('email' => $email));

You can use updateOrCreate:

$user = App\User::query()->firstWhere('email', '[email protected]');

$user->sandwiches()->updateOrCreate(['user_id' => $user->id], [
    'cabbage' => false,
    'bacon' => 9001,
]);

updateOrCreate has two parameters. The first one is the match condition(s). The second one is the upsert data. For example, if there is no row with user_id === $user->id, a record will be created with that and the fields from the second parameter.

This won't work, you have to do it manually/directly using User model because users() should return a collection object

This is correct, the users() function does not return a (new, empty or created) User model, it returns a collection object.

It's also documented http://laravel.com/docs/5.1/eloquent-relationships#inserting-related-models if you use the laravel relations than it should work.

You are misinterpreting that document. The relationship object has a create() method and a save() method, however the relationship object is not a full model object. To get all of the functionality of a full User model object (such as firstOrCreate()) then you have to call them on the model object.

So, for example, this code should work:

$user = User::firstOrNew(array('email' => $email));
Client::find($id)->users()->save($user);

Note that it should be OK to save the $user object here directly from the Client model's relationship, even though it may already exist here, it should just update the client_id field on the $user object when you do so.