Summary: For a (molecular) graph, the first and second Zagreb indices (\(M_1\) and \(M_2\)) are two well-known topological indices in chemical graph theory introduced by I. Gutman and N. Trinajstić [“Graph theory and molecular orbitals. Total \(\varphi\)-electron energy of alternant hydrocarbons”, Chem. Phys. Lett. 17, 535–538 (1972; doi:10.1016/0009-2614(72)85099-1)]. Let \(\mathcal{G}_{n,m}\) be the set of connected graphs of order \(n\) and with \(m\) edges. In this paper we characterize the extremal graphs from \(\mathcal{G}_{n,m}\) with \(n + 2\ge m \ge 2n-4\) with maximal first Zagreb index and from \(\mathcal{G}_{n,m}\) with \(m-n = \binom{k}{2}-k\) for \(k\ge 4\) with maximal second Zagreb index, respectively. Finally a related conjecture has been proposed to the extremal graphs with respect to second Zagreb index.