Enteroviruses elicit protective mucosal immune responses that could be harnessed as part of a strategy to prevent sexual transmission of the human immunodeficiency virus-1 (HIV-1). We report the construction of replication-competent recombinant vectors of coxsackievirus B3 (CVB3) that express one or more portions of the HIV-1 Gag protein. Vectors containing the capsid domain of Gag were initially genetically unstable with protein expression lost after brief passage in tissue culture. Codon modification to increase the G/C content of the HIV-1 capsid sequence resulted in enhanced genetic stability of CVB3 vectors during in vitro passage. Cells infected with a vector expressing the matrix (MA) subunit of the HIV-1 Gag protein were susceptible to lysis by CD8 T cell clones specific for the SL9 epitope found within MA. These studies suggest that CVB3 vectors may be useful as vaccine vector candidates, if hurdles in class I antigen presentation and stability can be overcome.