We present a comprehensive study of the critical current densities and the superconducting vortex phase diagram in the stoichiometric superconductor CaKFe$_4$As$_4$ which has a critical temperature of 35 K. We performed detailed magnetization measurements both of high quality single crystals for different orientations in an applied magnetic field up to 16 T and for a powder sample. We find an extremely large critical current density, Jc, up to 10$^8$ A/cm2 for single crystals when H||(ab) at 5 K, which remains robust in fields up to 16 T, being the largest of any other iron-based superconductor. The critical current density is reduced by a factor 10 in single crystals when H||c at 5 K and significantly suppressed by the presence of grain boundaries in the powder sample. We also observe the presence of the fishtail effect in the magnetic hysteresis loops of single crystals when H||c. The flux pinning force density and the pinning parameters suggest that the large critical current could be linked to the existence of point core and surface pinning. Based on the vortex phase diagram and the large critical current densities, CaKFe$_4$As$_4$ is now established as a potential iron-based superconductor candidate for practical applications.