You can have Objects without classes, certainly - even C had structs, and all functional languages I know of have records or something similar.

It's a question of terminology whether you call that object-oriented. It's certainly part of OO, in any case.