According to the database of the 1880 Census, Dist. 3, Walla Walla, WA, Henry TEVIS, 38, and his parents were born in Germany.He was with wf. Lottie M., 26, OR AR MO; son Frank, 3, OR; & dau. May May, 11 mos., b. WA Terr.
Since Lottie, 26, & Frank, 3, were both born in Oregon, there should be a record of marriage about 1876 in Oregon.
Do the other clues you have indicate an immigrant?