We study reflexivity and structure properties of operator algebras generated by representations of the discrete Heisenberg semi-group. We show that the left regular representation of this semi-group gives rise to a semi-simple reflexive algebra. We exhibit an example of a representation which gives rise to a non-reflexive algebra. En route, we establish reflexivity results for subspaces of $H^{infty}(bb{T})otimescl B(cl H)$.