Previously we were awarded Gemini strategic funding to procure two custom medium-band K-band filters for the FLAMINGOS2 (F2) imager. These filters split the 2.0-2.5 micron window in two, and are specifically suitable to trace the important Balmer/4000 Angstrom feature in galaxies at z>4. Building on the success of our ZFOURGE survey, which used medium-band J and H filters to explore the 2 < z < 4 universe, the new medium-band K-band filters push galaxy census surveys firmly into a new frontier: 4 < z < 6. Here, we propose ZF2K: a large F2 imaging program with these medium-band filters, covering a total of 0.5 sq. deg. spread over three premier deep fields (COSMOS, UDS, and GOODS-S). Our primary goals are (1) to characterise the rapidly evolving population of very massive galaxies (log M/ Msol >10.9) at z > 4, probing the first 0.5-1.5 Gyr of cosmic history, 2) to identify intense starbursts with strong nebular emission lines (eg. [OIII]5008) at 2 < z < 5, which are important in the context of low- mass galaxy formation and cosmic reionization, and 3) the identification of metal-free nebulae in the very early universe (z > ~15), including those ionized by Direct Collapse Black Holes (DCBH). While our survey strategy is principally designed to maximise the number of massive galaxies detected at z > 4, we expect to see hundreds of emission line galaxies, and ~50 DCBHs. All will be natural targets for detailed, pointed follow up with ALMA and JWST. ZFK2 thus represents unique, transformative science in multiple regimes, which can only be done with Gemini and these custom filters. As the JWST era approaches, now is the time to capitalise on the substantial strategic investment that Gemini has made by building this unique capacity.