We present the first computation in a program of lattice-QCD baryon physics using staggered fermions for sea and valence quarks. For this initial study, we present a calculation of the nucleon mass, obtaining $964pm16$ MeV with all sources of statistical and systematic errors controlled and accounted for. This result is the most precise determination to date of the nucleon mass from first principles. We use the highly-improved staggered quark action, which is computationally efficient. Three gluon ensembles are employed, which have approximate lattice spacings $a=0.09$ fm, $0.12$ fm, and $0.15$ fm, each with equal-mass $u$/$d$, $s$, and $c$ quarks in the sea. Further, all ensembles have the light valence and sea $u$/$d$ quarks tuned to reproduce the physical pion mass, avoiding complications from chiral extrapolations or nonunitarity. Our work opens a new avenue for precise calculations of baryon properties, which are both feasible and relevant to experiments in particle and nuclear physics.