In this paper, we study a new kind of vertex operator algebras related to twisted Heisenberg-Virasoro algebra. We showed that there exist one-to-one correspondences between the restricted module categories of twisted Heisenberg-Virasoro algebras of rank one and rank two and several different kinds of module categories of their corresponding vertex algebras. We also study in detail the structures of the twisted Heisenberg-Virasoro vertex operator algebra and give a characterization of it as a tensor product of two well-known vertex operator algebras.