Developing a safe and effective vaccine remains a global priority for ending the human immunodeficiency virus (HIV) pandemic. All HIV vaccine trials with protein, DNA, non-replication vector or their combinations failed in the past. We constructed the HIV-1 CN54 env, gag, and pol genes into both DNA and replicating vaccinia virus Tiantan vectors. In phase Ia, 12 healthy adults were given high (n = 6) or low (n = 6) doses of recombinant vaccinia virus Tiantan vaccine (rTV), to test its safety dose. In phase Ib, 36 healthy adults were assigned to the DNA (n = 6), DNA-L/rTV (n = 12), DNA-H/rTV (n = 12), and placebo (n = 6) groups. The DNA vaccine was injected intramuscularly at weeks 0, 4, and 8 and rTV with a bifurcated needle at week 12. All vaccines tested were safe and well-tolerated; most of the adverse events (AEs) were mild to moderate. The most commonly observed AEs were redness and papule at rTV vaccination sites and axillary enlarged lymph nodes at the same rTV vaccination arm. Smaller cutaneous lesions and shorter healing time were observed in smallpox vaccine experienced subjects. The DNA prime-rTV boost regimen induced anti-gp120 IgG and polyfunctional CD4 T cells. No significant differences of anti-HIV IgG and T cell responses were found between the two prime-boost groups with high and low DNA doses. Moreover, smallpox vaccine naïve subjects elicited higher T cell responses and anti-gp120 antibodies. The result of this trial supports further development of HIV vaccine with DNA and replicating vaccinia vector for advanced clinical trials.