Human adenovirus (Ad) vectors are extensively used as gene transfer vehicles. However, a serious obstacle for the use of these vectors in clinical applications is due to pre-existing immunity to human Ads affecting the efficacy of gene transfer. One of the approaches to circumvent host immune response could be the development of vectors based on non-human Ads that are able to transduce genes into human cells. In this study, we explored the possibility of using avian Ad CELO vectors as gene-transfer vehicles. For this purpose, we constructed a set of recombinant CELO viruses and demonstrated that they are able to deliver transgenes into various organs on the background of pre-existing immunity to human Ad5. The created CELO-p53 vector restored the function of the p53 tumor suppressor both in cultured human tumor cells in vitro and in their xenografts in nude mice in vivo. The latter effect was accompanied by inhibition of tumor growth. Noteworthily, the delivery of CELO-p53 led to activation of p53 target genes in cells showing inactivation of endogenous p53 by three different mechanisms, that is, in the human epidermoid carcinoma A431, lung adenocarcinoma H1299, and cervical carcinoma HeLa.