Human Papillomaviruses (HPV) are one of the most prevalent sexually transmitted infections (STI) and the most oncogenic viruses known to humans. The vast majority of HPV infections clear in less than 3 years, but the underlying mechanisms, especially the involvement of the immune response, are still poorly known. Building on earlier work stressing the potential importance of stochasticity in HPV infection clearance, we develop a stochastic mathematical model of HPV dynamics with an explicit description of the intracellular level. We show that the random partitioning of virus episomes upon stem cell division and the occurrence of symmetric divisions greatly affect viral persistence. These results call for more detailed within-host studies to better understand the relative importance of stochasticity and immunity in HPV infection clearance.