The all-sky very-high energy (104 − 106 GeV) atmospheric muon flux is most recently measured by IceCube, where in the higher energy range, the spectrum hardens indicating a prompt component. IceCube also measures the atmospheric muon neutrino flux at high energy. Since this is dominated by the astrophysical flux, they are only able to set an upper bound on the prompt atmospheric muon neutrino flux contribution. We provide a new evaluation of the prompt atmospheric muon flux including for the first time an intrinsic charm component to colliding nucleons. This increases forward production of D-mesons and baryons, which decay into final states that can contain muons and muon neutrinos. We show how the increase in the prompt muon flux due to intrinsic charm has an associated increase in the prompt muon neutrino flux. We consider the Regge ansatz for intrinsic charm production that we implement in MCEq used for the calculation of the lepton fluxes. We discuss the challenges of obtaining predictions that are simultaneously consistent with both IceCube’s high energy atmospheric muon flux measurements and the experimental upper bound on the prompt muon neutrino flux. We quantify the discrepancies.