Let's compare three sentences (assuming that we are allowed to use only will for the future tense for comparison) as follows:
(1) I believe that Mary arrived.
(2) I believe that Mary will
Now, contrast the above two sentences with the below one:
(3) *I believe Mary to arrive. (ungrammatical with *)
As you can clearly notice, you can never tell whether No. (3) means (1) or (2). It is a very important difference in context where you need to clarify a tense of the verb. (the time of arriving).
To infinitive is called infinitive because it can't inflect for tense and person. In order to clearly specify the tense, you should not use to infinitive.
Now, contrast the above (1) and (2) with your example:
(4) I believed (that) he was honest. = (5) I believed him (to be)
Believed and was in No. (4) used the past tense. There could be no confusion.
In No. (5), there is only one tense, i.e. believed which is the past tense. However, you can use to-infinitive because it indicates the same tense as believed. Also, to be could be omitted as it is not absolutely necessary and the adjective honest could function as an object complement on its own.
There are many English transitive verbs that can't be used in the No. (3) structure, i.e.:
*I think him to come tomorrow. *I hope him to come tomorrow. *I guess him to come tomorrow.
Not only are they ungrammatical, but they don't sound natural.
I want you to tell me the truth. I hope to see you soon.
The above two sentences are all grammatically correct as there is no particular reason to specify any tense for to tell the truth and to see.
The above explanation doesn't cover all transitive verbs in English and you need to learn how to use them on a case-by-case basis.
However, if you focus on tense, object, object complement and that-clause after a verb, you would easily understand some patterns for English verbs. The following link explains Verb + object + TO-infinitive structure. And this link lists the verbs that have Verb + that-clause structure.