We present the first ab initio calculations for p-shell single-Lambda hypernuclei. For the solution of the many-baryon problem, we develop two variants of the no-core shell model with explicit $\Lambda$ and $\Sigma^+$, $\Sigma^0$, $\Sigma^-$ hyperons including $\Lambda$-$\Sigma$ conversion, optionally supplemented by a similarity renormalization group transformation to accelerate model-space convergence. In addition to state-of-the-art chiral two- and three-nucleon interactions, we use leading-order chiral hyperon-nucleon interactions and a recent meson-exchange hyperon-nucleon interaction. We validate the approach for s-shell hypernuclei and apply it to p-shell hypernuclei, in particular to $^7_\Lambda$Li, $^9_\Lambda$Be and $^{13}_\Lambda$C. We show that the chiral hyperon-nucleon interactions provide ground-state and excitation energies that agree with experiment within the cutoff dependence. At the same time we demonstrate that hypernuclear spectroscopy provides tight constraints on the hyperon-nucleon interactions and we discuss the impact of induced hyperon-nucleon-nucleon interactions.