We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on $n$ vertices can be decomposed into at most $\left\lceil \frac{n}{2}\right\rceil$ paths, while a conjecture of Hajós states that any Eulerian graph on $n$ vertices can be decomposed into at most $\left\lfloor \frac{n-1}{2}\right\rfloor$ cycles. The Erdős-Gallai conjecture states that any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. We show that if $G$ is a sufficiently large graph on $n$ vertices with linear minimum degree, then the following hold. (i) $G$ can be decomposed into at most $\frac{n}{2}+o(n)$ paths. (ii) If $G$ is Eulerian, then it can be decomposed into at most $\frac{n}{2}+o(n)$ cycles. (iii) $G$ can be decomposed into at most $\frac{3 n}{2}+o(n)$ cycles and edges. If in addition $G$ satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such $G$. (iv) $G$ can be decomposed into $\max \left\{\frac{odd(G)}{2},\frac{Δ(G)}{2}\right\}+o(n)$ paths, where $odd(G)$ is the number of odd-degree vertices of $G$. (v) If $G$ is Eulerian, then it can be decomposed into $\frac{Δ(G)}{2}+o(n)$ cycles. All bounds in (i)-(v) are asymptotically best possible.