Escreve-se Provedoria da Justiça (com iniciais maiúsculas), dado que se trata de uma instituição; e grafa-se provedor da Justiça, da mesma forma que se escreve, por exemplo, ministro da Justiça ou procurador-geral da Justiça. Contudo, em certas circunstâncias (por exemplo, correspondência endereçada a quem exerce tais cargos), convém empregar maiúsculas nos dois substantivos que constituem cada expressão: Ministro da Justiça e Procurador-Geral da República.