TL;DR
Eu respondo isso em boa medida na pergunta Qual é o paradigma de programação usado pelo JavaScript?. Então já começo dizendo que JavaScript é multi-paradigma, entre eles a orientação a objeto.
Introdução
Falo sobre O que é paradigma?. Por essa definição JS é essencialmente imperativa e possui alguns recursos que facilitam a orientação a objeto. É importante entender Qual a diferença entre uma classe e um objeto?.
Falo sobre o Significado da terminologia "Orientado a objeto". Ali não há uma resposta definitiva, há muita controvérsia sobre o que OOP realmente é. Vou falar aqui no que é mais aceito em programação (não em design) e que pode ajudar definir se a linguagem é ou não orientada a objeto. Lá define o que é um objeto que é importante para começarmos entender se há orientação.
Há outras definições que não gosto tanto: O que é "Orientado a objeto" e quais outros métodos?. Também há questionamento se Existe classe em JavaScript? e é um leitura importante. Leitura complementar: Programação Funcional e Programação Orientada a Objetos. O que são e quais suas principais diferenças?.
Lembrando que você pode fazer orientação a objeto até em Assembly. Ou em C: É possível programar orientado a objeto em C?.
Não é tão claro se é ou não
Por todas definições que encontrei JS é OO (como paradigma secundário). Em menor grau que outras linguagens. Ela é mais especificamente orientada a protótipos, que não deixam de ser objetos. A orientação a protótipos é um ramo da orientação a objetos. A Linguagem não é orientada à classes.
Se ainda não acredita, leia a documentação que é considerada oficial. Note que eles não falam que a linguagem é orientada a objeto. De uma certa forma nenhuma linguagem é de um paradigma. Você aplica paradigmas no seu código. Mas é claro que as linguagens incentivam um certo paradigma.
JS incentiva a orientação a objeto? Depende da definição de OOP que você use e depende da definição do que é incentivar.
Você chama membros de uma estrutura, incluindo funções/métodos, se referenciando pelo objeto primariamente. Alguns dizem que isso já é suficiente para ser orientado a objeto. Outros dirão que precisa poder fazer herança, polimorfismo e encapsulamento.
- Um objeto pode ser criado baseado em outro existente - que será um protótipo deste (veja exemplo em outras respostas);
- um objeto pode assumir comportamentos diferentes de forma consistente com sua "família";
- um objeto pode esconder os detalhes de como ele funciona.
Pode-se argumentar que a sintaxe não é a mais conveniente para fazer isso. Mas bem fácil entender o funcionamento. Há mecanismo específicos que "incentivam" fazer essas coisas. Se eles são suficientes eu não sei, acho que aí caímos na subjetividade. Objetivamente os mecanismos existem.
Alguns falam que é necessário abstração e/ou sobrecarga de operadores. Mas são poucas fontes que citam essas características como obrigatórias e não são as mais confiáveis. É possível fazer abstração em JS, mas não há mecanismo específico. De qualquer forma é uma coisa mais de design. Sobrecarga de operador realmente não tem nada, mas é um recurso controverso se faz parte de OO. Java não faz isso e ninguém questiona se a linguagem é orientada a objeto.
Pra falar a verdade conheço muita gente que não acha a sintaxe de classe tão conveniente assim. Claro, estão tão acostumados com os protótipos que dificulta a adaptação.
Por outro lado há quem fale que OOP é sobre o reúso de código. JS é uma das linguagens mais simples de obter isso. Se disser que OO é colocar estado junto com comportamento, é bem fácil, o fato de ser opcional fazer isso não muda nada.
Não há pureza em JS. Mas qual linguagem é pura? E nem é uma boa característica.
O fato dela ser orientada a protótipos não elimina o fato de ser orientada a objetos também, assim como não elimina o fato de ser principalmente imperativa.
ES6
EcmaScript6 trouxe as classes para a linguagem. Note que não houve alterações semânticas importantes. Basicamente existe uma nova sintaxe para fazer o que já era possível, agora com classes. Sintaxe é importante, claro. Sempre dizemos que C pode ser programada orientada a objeto, mesmo sem a linguagem ser. JS não tinha facilidades para escrever classes, ainda que os objetos podiam ser criados sem elas.
Agora JS é orientada a protótipos e à classes. Mudou alguma coisa em relação a orientação a objetos? Me parece que não. Se não mudou nada, parece que a linguagem já era orientada a objeto antes de existir classes.
Quem não pode usar ES6, pode usar TypeScript e ter a orientação a objeto em sua forma clássica (veja mais).
Conclusão
Eu considero que a linguagem pode ser chamada de orientada a objeto, acho que a maioria das pessoas acham assim. Faz pouca diferença prática saber disso, mas é uma informação útil que pode ajudar entender melhor o que está fazendo, o que eu sempre defendo.
Coloquei no GitHub para referência futura.