We construct a minimum cycle basis for the direct product G × C_q where G is a connected non-bipartite graph and C_q is an odd cycle. These bases are expressed in terms of the cycle structure of the symmetric digraph on G.