Wir hielten ihn für unschuldig.

jdn/etw für jdn/etw halten - to take sb/sth for [or to be] sb/sth (PONS dictionary)