We show, by means of ab-initio calculations, that electron-electron correlations play an important role in potassium-doped picene ($K_x$-picene), recently characterized as a superconductor with $T_c = 18K$. The inclusion of exchange interactions by means of hybrid functionals reproduces the correct gap for the undoped compound and predicts an antiferromagnetic state for $x=3$, where superconductivity has been observed. The latter finding is compatible with a sizable value of the correlation strength, in agreement with simple estimates. Our results highlight the similarity between potassium-doped picene and alkali-doped fulleride superconductors.