Nanoparticle-mediated plasmid delivery is considered a useful tool to introduce foreign DNA into the cells for the purpose of DNA vaccination and/or gene therapy. Cationic solid-lipid nanoparticles (cSLNs) are considered one of the most promising non-viral vectors for nucleic acid delivery. Based on the idea that the optimization of the components is required to improve transfection efficiency, the present study aimed to formulate and characterize cholesteryl oleate-containing solid-lipid nanoparticles (CO-SLNs) incorporating protamine (P) to condense DNA to produce P:DNA:CO-SLN complexes as non-viral vectors for gene delivery with reduced cytotoxicity and high cellular uptake efficiency. For this purpose, CO-SLNs were used to prepare DNA complexes with and without protamine as DNA condenser and nuclear transfer enhancer. The main physicochemical characteristics, binding capabilities, cytotoxicity and cellular uptake of these novel CO-SLNs were analyzed. Positively charged spherical P:DNA:CO-SLN complexes with a particle size ranging from 330.1 ± 14.8 nm to 347.0 ± 18.5 nm were obtained. Positive results were obtained in the DNase I protection assay with a protective effect of the genetic material and 100% loading efficiency was achieved at a P:DNA:CO-SLN ratio of 2:1:7. Transfection studies in human embryonic kidney (HEK293T) cells showed the versatility of adding protamine to efficiently transfect cells, widening the potential applications of CO-SLN-based vectors, since the incorporation of protamine induced almost a 200-fold increase in the transfection capacity of CO-SLNs without toxicity. These results indicate that CO-SLNs with protamine are a safe and effective platform for non-viral nucleic acid delivery.